首页 > 代码库 > SPOJ 375 Query on a tree

SPOJ 375 Query on a tree

Desciption

给出一个树,每条边有边权,支持两种操作,询问 \(u,v\) 路径上边权最大值,修改第 \(i\) 条边的边权,\(n\leqslant 10^4,T\leqslant 10\)

Sol

树链剖分.

基于边的树链剖分,对于一个点,可能有许多儿子,但是它只能有一个父亲,给它编号表示它到它父亲的边,只需要修改查询的是最后一步就可以了.

Code

#include<cstdio>#include<vector>#include<iostream>using namespace std;#define debug(a) cout<<#a<<"="<<a<<" "#define mid ((l+r)>>1)#define lc (o<<1)#define rc (o<<1|1)const int N = 10005;inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘||ch<‘0‘) ch=getchar();	while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x; }int n,e,cnt;struct Edge{ int fr,to,v; }edge[N];vector<Edge> g[N];int f[N],cost[N],dep[N],son[N],top[N],sz[N],p[N];int d[N<<2];void Add_Edge(int fr,int to,int v){	edge[++e]=(Edge){ fr,to,v };	g[fr].push_back((Edge){ fr,to,v });	g[to].push_back((Edge){ to,fr,v });}void DFS1(int u,int fa){	sz[u]=1,son[u]=0,dep[u]=dep[fa]+1,f[u]=fa;	for(int i=0,lim=g[u].size(),v;i<lim;i++) if((v=g[u][i].to)!=fa){		DFS1(v,u),sz[u]++;		if(!son[u]||sz[son[u]]<sz[v]) son[u]=v;	}}void DFS2(int u,int tp){	p[u]=++cnt,top[u]=tp;	if(son[u]) DFS2(son[u],tp);	for(int i=0,lim=g[u].size(),v;i<lim;i++) if((v=g[u][i].to)!=f[u]&&v!=son[u])		DFS2(v,v);}void Build(int o,int l,int r){	if(l==r){ d[o]=cost[l];return; }	Build(lc,l,mid),Build(rc,mid+1,r);	d[o]=max(d[lc],d[rc]);}void Change(int o,int l,int r,int x,int v){	if(l==r){ d[o]=v;return; }	if(x<=mid) Change(lc,l,mid,x,v);	else Change(rc,mid+1,r,x,v);	d[o]=max(d[lc],d[rc]);}int QueryMax(int o,int l,int r,int L,int R){	if(L<=l&&r<=R) return d[o];int res=0;	if(L<=mid) res=max(res,QueryMax(lc,l,mid,L,R));	if(R>mid) res=max(res,QueryMax(rc,mid+1,r,L,R));	return res;}int GetAns(int u,int v){	int res=0,f1=top[u],f2=top[v];	while(f1!=f2){		if(dep[f1]<dep[f2]) swap(u,v),swap(f1,f2);		res=max(res,QueryMax(1,1,n,p[f1],p[u]));		u=f[f1],f1=top[u];	}	if(dep[u]>dep[v]) swap(u,v);	if(dep[v]==dep[u]) return res;	else return max(res,QueryMax(1,1,n,p[u]+1,p[v]));}void clr(){ for(int i=0;i<N;i++) g[i].clear();cnt=0,e=0; }int main(){//	freopen("in.in","r",stdin);//	freopen("out.out","w",stdout);	ios::sync_with_stdio(false);	for(int T=in();T--;){		clr();		n=in();		for(int i=1,a,b,c;i<n;i++) a=in(),b=in(),c=in(),Add_Edge(a,b,c);		DFS1(1,1),DFS2(1,1);				for(int i=1;i<n;i++){			int a=edge[i].fr,b=edge[i].to;			if(dep[a]>dep[b]) swap(a,b),swap(edge[i].fr,edge[i].to);			cost[p[b]]=edge[i].v;		}				Build(1,1,n);		for(char opt[10];;){			scanf("%s",opt);			if(opt[0]==‘D‘) break;			int a=in(),b=in();			if(opt[0]==‘C‘) Change(1,1,n,p[edge[a].to],b);			else printf("%d\n",GetAns(a,b));//			debug(QueryMax(1,1,n,1,1)),debug(QueryMax(1,1,n,2,2)),debug(QueryMax(1,1,n,3,3))<<endl;		}	}return 0;}

  

 

SPOJ 375 Query on a tree