2018.03.19【SPOJ-QTREE】Query on a tree（輕重鍊剖分）（線段樹）（DFS序）

傳送門

過于基礎不想寫題解，寫LCT寫久了忘了樹剖怎麼寫了來複習一下。

代碼：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define gc get_char
#define cs const

namespace IO{
	inline char get_char(){
		static cs int Rlen=1<<20|1;
		static char buf[Rlen],*p1,*p2;
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++; 
	}
	
	inline int getint(){
		re char c;
		while(!isdigit(c=gc()));re int num=c^48;
		while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
		return num;
	}
	inline char getalpha(){
		re char c;
		while(!isalpha(c=gc()));return c;
	}
}
using namespace IO;

using std::cout;
typedef std::pair<int,int> pii;
#define mp std::make_pair

cs int N=1e4+4;

int n;
std::vector<pii> e[N];
inline void addedge(int u,int v,int id){
	e[u].push_back(mp(v,id));
	e[v].push_back(mp(u,id));
}

int siz[N],fa[N],top[N],dep[N],son[N];
int dfs_clock,in[N],pos[N];
int down[N],val[N],w[N];
void dfs1(int u){
	siz[u]=1;
	for(pii &e:(::e[u]))
	if(e.first!=fa[u]){
		int v=e.first;
		down[e.second]=v;
		val[v]=w[e.second];
		fa[v]=u;
		dep[v]=dep[u]+1;
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}

void dfs2(int u){
	pos[in[u]=++dfs_clock]=u;
	if(son[u]){
		top[son[u]]=top[u];
		dfs2(son[u]);
	}
	else return ;
	for(pii &e:(::e[u]))
	if(e.first!=fa[u]&&e.first!=son[u]){
		top[e.first]=e.first;
		dfs2(e.first);
	}
}

int mx[N<<2];

inline void build(int k,int l,int r){
	if(l==r){
		mx[k]=val[pos[l]];
		return ;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	mx[k]=std::max(mx[k<<1],mx[k<<1|1]);
}

inline int query(int k,int l,int r,cs int &ql,cs int &qr){
	if(ql<=l&&r<=qr)return mx[k];
	int mid=(l+r)>>1;
	if(qr<=mid)return query(k<<1,l,mid,ql,qr);
	if(mid<ql)return query(k<<1|1,mid+1,r,ql,qr);
	return std::max(query(k<<1,l,mid,ql,qr),query(k<<1|1,mid+1,r,ql,qr));
}

inline void modify(int k,int l,int r,cs int &pos,cs int &val){
	if(l==r){
		mx[k]=val;
		return ;
	}
	int mid=(l+r)>>1;
	if(pos<=mid)modify(k<<1,l,mid,pos,val);
	else modify(k<<1|1,mid+1,r,pos,val);
	mx[k]=std::max(mx[k<<1],mx[k<<1|1]);
}

inline int query(int u,int v){
	int ans=-0x3f3f3f3f;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])std::swap(u,v);
		ans=std::max(ans,query(1,1,n,in[top[u]],in[u]));
		u=fa[top[u]];
	}
	if(u==v)return ans;
	if(dep[u]>dep[v])std::swap(u,v);
	return std::max(ans,query(1,1,n,in[u]+1,in[v]));
}

inline void solve(){
	n=getint();
	for(int re i=1;i<n;++i){
		addedge(getint(),getint(),i);
		w[i]=getint();
	}
	dfs1(1);top[1]=1;dfs2(1);
	build(1,1,n);
	while(true){
		switch(getalpha()){
			case 'D':return ;
			case 'Q':{
				cout<<query(getint(),getint())<<"\n";
				break;
			}
			case 'C':{
				int id=getint(),val=getint();
				modify(1,1,n,in[down[id]],val);
				break;
			}
		}
	}
}

inline void init(){
	for(int re i=1;i<=n;++i)e[i].clear();
	memset(son+1,0,sizeof(int)*n);
	dfs_clock=0;
}

int T;
signed main(){
	T=getint();
	while(T--){
		init();
		solve();
	}
	return 0;
}