http://www.zybbs.org/JudgeOnline/problem.php?id=1036

用轻重边树链剖分写了下……由于已经写了QTREE3了所以这个很快就写出来了……而且速度也还理想……（真心懒得再写个树状数组……）囧……剖的东西看我的QTREE3代码罢……

#include <stdio.h>
#include <string.h>
int n,m,a[2][65536],as=-1,r[30001],f[30001],s[30001],l[30001],d[30001],w[30001],de[30001],ans,t;
struct edge{struct edge *next;int y;}*map[30001],st[60000],*h[30001];
getint(){
	int re=0,ch=getchar(),k;
	while((ch<'0'||ch>'9')&&ch!='-')if((ch=getchar())<=0)return -1;
	for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?-re:re;
}void make(i){
	struct edge *p=map[i],*q;int k,dp;
	for(l[i]=s[i]=1;p;p=p->next)if(p->y!=f[i]){
		f[p->y]=i;de[p->y]=de[i]+1;make(p->y);s[i]+=s[p->y];
		if(i&&(!h[i]||s[h[i]->y]<s[p->y]))l[i]=l[(h[i]=p)->y]+1;
	}for(p=map[i];q=p;p=p->next)if(p->y!=f[i]&&p!=h[i]){
		for(k=p->y;l[k]!=(l[k]&-l[k]);l[k]+=l[k]&-l[k]);
		for(dp=0;q;q=h[q->y]){
			a[0][(s[q->y]=as)+(l[q->y]=l[r[q->y]=k])+(d[q->y]=dp)]=w[q->y];
			a[1][as+l[k]+dp++]=w[q->y];
		}for(dp=l[k]-1;dp>0;dp--){
			a[0][s[k]+dp]=a[0][s[k]+(dp<<1)]>a[0][s[k]+(dp<<1^1)]?a[0][s[k]+(dp<<1)]:a[0][s[k]+(dp<<1^1)];
			a[1][s[k]+dp]=a[1][s[k]+(dp<<1)]+a[1][s[k]+(dp<<1^1)];
		}as+=(l[k]<<1)-1;
	}
}__inline void update(s,x,y){
	for(x=l[x]+d[x]-1,y=l[y]+d[y]+1;x^y^1;x>>=1,y>>=1){
		if(~x&1){
			if(t=='S')ans+=a[1][s+(x^1)];
			else if(ans<a[0][s+(x^1)])ans=a[0][s+(x^1)];
		}if(y&1){
			if(t=='S')ans+=a[1][s+(y^1)];
			else if(ans<a[0][s+(y^1)])ans=a[0][s+(y^1)];
		}
	}
}main(){
	int i,x,y,z[2],xx;
	(map[0]=st)->y=1;
	for(i=(n=getint())-1<<1;i;i-=2){
		st[i^1].y=x=getint();st[i].y=y=getint();
		st[i].next=map[x];st[i^1].next=map[y];
		map[x]=st+i;map[y]=st+(i^1);
	}for(i=1;i<=n;i++)w[i]=getint();
	memset(a[0],0x8F,n<<3);
	for(make(0),m=getint(),getchar();m--&&(t=getchar(),z[0]=getint(),z[1]=getint(),getchar());)if(t!='H'){
		for(ans=t=='M'?0x8F8F8F8F:0;r[z[0]]!=r[z[1]];z[i]=f[r[z[i]]]){
			xx=z[i=de[r[z[0]]]==de[r[z[1]]]?de[z[0]]>de[z[1]]?0:1:de[r[z[0]]]>de[r[z[1]]]?0:1];
			update(s[xx],r[xx],xx);
		}update(s[z[0]],z[de[z[0]]>de[z[1]]],z[de[z[0]]<de[z[1]]]);
		printf("%d\n",ans);
	}else for(a[0][s[z[0]]+l[z[0]]+d[z[0]]]=a[1][s[z[0]]+l[z[0]]+d[z[0]]]=z[1],z[1]=l[z[0]]+d[z[0]]>>1;z[1];z[1]>>=1){
		a[0][s[z[0]]+z[1]]=a[0][s[z[0]]+(z[1]<<1)]>a[0][s[z[0]]+(z[1]<<1^1)]?a[0][s[z[0]]+(z[1]<<1)]:a[0][s[z[0]]+(z[1]<<1^1)];
		a[1][s[z[0]]+z[1]]=a[1][s[z[0]]+(z[1]<<1)]+a[1][s[z[0]]+(z[1]<<1^1)];
	}return 0;
}

以下是以前的做法（块状树）：

用WJBZBMR神犇的块状树做的。。2K代码内牛满面。LCT等等5K代码退散啊。。。

不过时间有点悲剧。。呃。。这算掐时过么。。

块状树&题解移步：http://hi.baidu.com/wjbzbmr/blog/item/3d7741a0ade48ba0cbefd085.htm

块状数据结构秒杀一切水题！秒杀一切水题！

#include <stdio.h>
#include <math.h>
int n,w[5][30000],sq,t;
struct edge{struct edge *next;int y;}map[30000],starr[59998],*tail[30000];
make(i,d,f){
	int s=1,sc;struct edge *p=map[i].next;
	for(w[3][i]=w[4][i]=w[0][i],w[1][i]=d,map[i].y=f;p;p=p->next)if(p->y!=f){
		sc=make(p->y,d+1,i);
		if(s+sc-sq<=10)s+=sc,w[2][p->y]=i;
	}return s;
}void dfs(i){
	struct edge *p=map[i].next;
	for(;p;p=p->next)if(p->y!=map[i].y&&w[2][p->y]!=p->y){
		w[3][p->y]=w[3][p->y]>w[3][i]?w[3][p->y]:w[3][i];
		w[4][p->y]+=w[4][i];
		w[2][p->y]=t;
		dfs(p->y);
	}
}void update(i){
	struct edge *p=map[i].next;
	w[3][i]=w[3][map[i].y]>w[0][i]&&w[2][i]!=i?w[3][map[i].y]:w[0][i];
	w[4][i]=(w[2][i]!=i?w[4][map[i].y]:0)+w[0][i];
	for(;p;p=p->next)if(p->y!=map[i].y&&w[2][p->y]!=p->y)update(p->y);
}static __inline void get(i,j,f){
	int ans=f==3?-30000:0;
	while(w[2][i]!=w[2][j]){
		if(w[1][w[2][i]]<w[1][w[2][j]])i^=j^=i^=j;
		ans=f==3?ans>w[3][i]?ans:w[3][i]:ans+w[4][i];
		i=map[w[2][i]].y;
	}while(i!=j){
		if(w[1][i]<w[1][j])i^=j^=i^=j;
		ans=f==3?ans>w[0][i]?ans:w[0][i]:ans+w[0][i];
		i=map[i].y;
	}printf("%d\n",f==3?ans>w[0][i]?ans:w[0][i]:ans+w[0][i]);
}static __inline getint(){
	int re=0,k=1;char ch=getchar();
	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	for(ch=='-'?ch=getchar(),k=0:0;ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?re:-re;
}main(){
	int x,y,i;
	char str[10];
	for(sq=sqrt(n=getint()),i=0;i<n;i++)tail[w[2][i]=i]=map+i;
	for(i=0;i<n-1;i++){
		x=getint()-1;
		(tail[x]=tail[x]->next=starr+(i<<1))->y=y=getint()-1;
		(tail[y]=tail[y]->next=starr+(i<<1)+1)->y=x;
		tail[x]->next=tail[y]->next=0;
	}for(i=0;i<n;i++)w[0][i]=getint();
	make(0,0,0);
	for(i=0;i<n;i++)if(w[2][i]==i)dfs(t=i);
	for(getint();scanf("%s",str)>0;){
		x=getint()-1;
		if(str[1]=='H')w[0][x]=getint(),update(x);
		else get(x,getint()-1,4-(str[1]=='M'));
	}return 0;
}

用LCT做了下，1A，不过有一个沙茶错误调了半天……还好数据没坑爹否则就……我真是太若了……

速度是剖的两倍……真是悲剧……懒得加IO优化了……

#include <stdio.h>
#define maxn 30000
#define max(a,b) ((a)>(b)?(a):(b))
struct edge{struct edge *next;int y}*map[maxn],stm[maxn<<1],*p;
typedef struct _Splay{struct _Splay *c[2],*f,*p;int v,m,s}Splay,*PSplay;
Splay null,st[maxn];int n,que[maxn],bq=-1,eq=1;
inline PSplay updt(PSplay x){x->s=x->c[0]->s+x->c[1]->s+x->v;x->m=max(max(x->c[0]->m,x->c[1]->m),x->v);return x;}
inline PSplay extr(PSplay x,_Bool c){while(x->c[c]!=&null)x=x->c[c];return x;}
inline PSplay node(PSplay x,PSplay p){x->f=x->c[0]=x->c[1]=&null;return x->p=p;}
inline PSplay rot(PSplay x){
	PSplay fx=x->f,ffx=fx->f;
	_Bool c=fx->c[1]==x,fc=ffx->c[1]==fx;
	if(fx!=&null){
		if((fx->c[c]=x->c[!c])!=&null)fx->c[c]->f=fx;
		if((x->f=ffx)!=&null)ffx->c[fc]=x;
		updt((fx->f=x)->c[!c]=fx);
	}return x;
}inline PSplay splay(PSplay x,PSplay p){
	if(x==&null)return x;for(;x->f!=p;rot(x))if(x->f->f!=p)rot((x->f->f->c[1]==x->f)==(x->f->c[1]==x)?x->f:x);
	return updt(x);
}inline getint(){
	int re=0,ch=getchar();_Bool k;
	while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1;
	for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?-re:re;
}inline PSplay Access(PSplay x){
	PSplay t=splay(x,&null);x->c[1]=x->c[1]->f=&null;
	while((x=splay(extr(x,0),&null))->p!=&null){
		splay(x->p,&null)->c[1]->f=&null;
		t=x=(x->p->c[1]=x)->f=x->p;
	}return t;
}main(){
	int i,x,y;PSplay q,t;
	node(st,null.f=null.c[0]=null.c[1]=&null)->m=-30000;
	for(i=(n=getint())<<1;i-=2;map[y]=(map[x]=stm+i)+1){
		stm[i].next=map[stm[i^1].y=x=getint()-1];
		stm[i^1].next=map[stm[i].y=y=getint()-1];
	}for(i=-1;++i!=n;st[i].v=st[i].m=st[i].s=getint());
	while(++bq!=eq)for(p=map[que[bq]];p;p=p->next)if(st+p->y!=st[que[bq]].p)node(st+(que[eq++]=p->y),st+que[bq]);
	for(n=getint();n--;){
		while((i=getchar())!='Q'&&i!='C');
		if(i=='C')((q=splay(st+getint()-1,&null))->v)=getint(),updt(q);
		else{
			i=getchar();Access(st+(x=getint()-1));
			t=(q=splay(Access(st+(y=getint()-1)),&null))->c[0];
			q->c[0]=st+x==q?&null:splay(st+x,&null);
			printf("%d\n",i=='M'?updt(q)->m:updt(q)->s);
			q->c[0]=t;updt(q);
		}
	}return 0;
}

• inline
• block