树链剖分

OI&ACM, 数据结构
  1. 1 【bzoj 1036】[ZJOI2008]树的统计Count
  2. 2 【bzoj 4034】[HAOI2015]T2
  3. 3 【bzoj 4196】[Noi2015]软件包管理器
  4. 4 树的查询（qtree）
  5. 5 种草地（grassplant）
  6. 6 查询树（tree）

树链剖分详解

1 【bzoj 1036】[ZJOI2008]树的统计Count

权值在点上，单点修改，询问路径上的MAX和SUM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int N=30001;
char s[10];
int n,x,y,totw,tot=1,Q,ans,f1,f2;
int a[N],fa[N],dep[N],size[N],son[N],top[N],w[N];
vector<int> to[N];
struct node{
	int l,r,ls,rs,maxx,sum;
}t[N*2];
void dfs1(int x)
{
	size[x]++;
	for(int i=0;i<to[x].size();i++)
	{
		int y=to[x][i];
		if(fa[x]==y) continue;
		fa[y]=x;dep[y]=dep[x]+1;
		dfs1(y);size[x]+=size[y];
		if(size[son[x]]<size[y]) son[x]=y;
	}
}
void dfs2(int x)
{
	int y=son[x];if(!y) return;
	top[y]=top[x];w[y]=++totw;dfs2(y);
	for(int i=0;i<to[x].size();i++)
	{
		y=to[x][i];
		if(fa[x]==y||son[x]==y) continue;
		top[y]=y;w[y]=++totw;dfs2(y);
	}
}
void Build(int root,int L,int R)
{
	t[root].l=L;t[root].r=R;
	if(L==R) 
	{
		t[root].sum=t[root].maxx=a[L];return;
	}
	int mid=(L+R)>>1;
	t[root].ls=++tot;Build(t[root].ls,L,mid);
	t[root].rs=++tot;Build(t[root].rs,mid+1,R);
	t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
	t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
}
void Change(int root,int num,int d)
{
	if(t[root].l==t[root].r)
	{
		t[root].sum=t[root].maxx=d;return;
	}
	int mid=(t[root].l+t[root].r)>>1;
	if(num<=mid) Change(t[root].ls,num,d);
	else Change(t[root].rs,num,d);
	t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
	t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
}
int Sum(int root,int L,int R)
{
	if(L<=t[root].l&&t[root].r<=R) return t[root].sum;
	int mid=(t[root].l+t[root].r)>>1,z=0;
	if(L<=mid) z+=Sum(t[root].ls,L,R);
	if(R>mid)  z+=Sum(t[root].rs,L,R);
	return z;
}
int Max(int root,int L,int R)
{
	if(L<=t[root].l&&t[root].r<=R) return t[root].maxx;
	int mid=(t[root].l+t[root].r)>>1,z=-30000;
	if(L<=mid) z=max(z,Max(t[root].ls,L,R));
	if(R>mid)  z=max(z,Max(t[root].rs,L,R));
	return z;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		to[x].push_back(y);to[y].push_back(x); 
	}
	dep[1]=1;dfs1(1);
	top[1]=1;w[1]=++totw;dfs2(1);
	for(int i=1;i<=n;i++) scanf("%d",&a[w[i]]);
	Build(1,1,n);
	scanf("%d",&Q);
	while(Q--)
	{
		scanf("%s%d%d",s,&x,&y);
		if(s[0]=='C')  Change(1,w[x],y);
		else if(s[1]=='M')
		{
			ans=-30000;
			while(1)
			{
				f1=top[x];f2=top[y];
				if(f1==f2)
				{
					if(w[x]<w[y]) ans=max(ans,Max(1,w[x],w[y]));
					else ans=max(ans,Max(1,w[y],w[x]));
					break;
				}
				else
				{
					if(dep[f1]<dep[f2])  swap(x,y),swap(f1,f2);
					ans=max(ans,Max(1,w[f1],w[x]));
					x=fa[f1];
				}
			}
			printf("%d\n",ans);
		}
		else
		{
			ans=0;
			while(1)
			{
				f1=top[x];f2=top[y];
				if(f1==f2)
				{
					if(w[x]<w[y]) ans+=Sum(1,w[x],w[y]);
					else ans+=Sum(1,w[y],w[x]);
					break;
				}
				else
				{
					if(dep[f1]<dep[f2])  swap(x,y),swap(f1,f2);
					ans+=Sum(1,w[f1],w[x]);
					x=fa[f1];
				}
			}
			printf("%d\n",ans);
		}
	}
}

2 【bzoj 4034】[HAOI2015]T2

操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

第二次dfs的时候求dfs序，按st[]建树，操作二就是修改st[]到ed[]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<cstdio>
#include<vector>
using namespace std;
const int N=100001;
int n,m,tot,totw,x,y,k,f1;
long long ans;
int size[N],fa[N],dep[N],st[N],ed[N],son[N],top[N],a[N],b[N];
vector<int> to[N];
struct node{
	int l,r,ls,rs;long long mark,sum;
}t[N*2];
void dfs1(int x)
{
	size[x]=1;
	for(int i=0;i<to[x].size();i++)
	{
		int y=to[x][i];
		if(fa[x]==y) continue;
		dep[y]=dep[x]+1;fa[y]=x;
		dfs1(y);size[x]+=size[y];
		if(size[son[x]]<size[y]) son[x]=y;
	}
}
void dfs2(int x)
{
	st[x]=ed[x]=++totw;
	if(!son[x]) return;
	int y=son[x];top[y]=top[x];dfs2(y);
	for(int i=0;i<to[x].size();i++)
	{
		y=to[x][i];
		if(y==fa[x]||y==son[x]) continue;
		top[y]=y;dfs2(y);
	}
	ed[x]=totw;
}
void push_down(int root)
{
	int L=t[root].ls,R=t[root].rs;
	if(!L&&!R) return;
	long long ma=t[root].mark;t[root].mark=0;
	t[L].mark+=ma;t[L].sum+=ma*(t[L].r-t[L].l+1);
	t[R].mark+=ma;t[R].sum+=ma*(t[R].r-t[R].l+1);
}
void Build(int root,int L,int R)
{
	t[root].l=L;t[root].r=R;
	if(L==R)
	{
		t[root].sum=b[L];return;
	}
	int mid=(L+R)>>1;
	t[root].ls=++tot;Build(t[root].ls,L,mid);
	t[root].rs=++tot;Build(t[root].rs,mid+1,R);
	t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
}
void add(int root,int L,int R,int d)
{
	if(t[root].mark) push_down(root);
	if(L<=t[root].l&&R>=t[root].r)
	{
		t[root].mark+=(long long)d;t[root].sum+=(long long)(t[root].r-t[root].l+1)*d;
		return;
	}
	int mid=(t[root].l+t[root].r)>>1;
	if(L<=mid) add(t[root].ls,L,R,d);
	if(R>mid)  add(t[root].rs,L,R,d);
	t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
}
long long Sum(int root,int L,int R)
{
	if(t[root].mark) push_down(root);
	if(L<=t[root].l&&t[root].r<=R) return t[root].sum;
	int mid=(t[root].l+t[root].r)>>1;long long sum=0;
	if(L<=mid) sum+=Sum(t[root].ls,L,R);
	if(R>mid)  sum+=Sum(t[root].rs,L,R);
	return sum;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		to[x].push_back(y);to[y].push_back(x);
	}
	dep[1]=1;top[1]=1;
	dfs1(1);dfs2(1);
	for(int i=1;i<=n;i++) b[st[i]]=a[i];
	tot=1;Build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&k,&x);
		if(k==1)
		{
			scanf("%d",&y);
			add(1,st[x],st[x],y);
		}
		else if(k==2)
		{
			scanf("%d",&y);
			add(1,st[x],ed[x],y);
		}
		else
		{
			ans=0;f1=top[x];
			while(f1!=1)
			{
				ans+=Sum(1,st[f1],st[x]);
				x=fa[f1];f1=top[x];
			}
			ans+=Sum(1,1,st[x]);
			printf("%lld\n",ans);
		}
	}
}

3 【bzoj 4196】[Noi2015]软件包管理器

install 向上求sum，并都改成1
uninstall 向下求sum，并都改成0

不要吐槽我把sum和change写一块儿了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<cstring>
#include<cstdio>
using namespace std;
const int N=100001;
int n,m,tot,x,ans,f;
int size[N],dep[N],fa[N],son[N],top[N],fi[N],ed[N];
int st[N],next[N],to[N];
char s[10];
struct node{
	int l,r,ls,rs,mark,sum;
}t[N*2];
void dfs1(int x)
{
	size[x]=1;dep[x]=dep[fa[x]]+1;
	for(int i=st[x];i;i=next[i])
	{
		int y=to[i];
		dfs1(y);size[x]+=size[y];
		if(son[x]==-1||(son[x]!=-1&&size[y]>size[son[x]])) son[x]=y;
	}
}
void dfs2(int x)
{
	fi[x]=ed[x]=++tot;
	if(son[x]==-1) return;
	int y=son[x];
	top[y]=top[x];dfs2(y);
	for(int i=st[x];i;i=next[i])
	{
		y=to[i];
		if(y==son[x]) continue;
		top[y]=y;dfs2(y);
	}
	ed[x]=tot;
}
void Build(int root,int L,int R)
{
	t[root].l=L;t[root].r=R;
	if(L==R) return;
	int mid=(L+R)>>1;
	t[root].ls=++tot; Build(tot,L,mid);
	t[root].rs=++tot; Build(tot,mid+1,R);
}
void push_down(int root)
{
	int ma=t[root].mark,L=t[root].ls,R=t[root].rs;
	t[L].mark=ma;t[L].sum=(t[L].r-t[L].l+1)*ma;
	t[R].mark=ma;t[R].sum=(t[R].r-t[R].l+1)*ma;
}
int Change(int root,int L,int R,int d)
{
	if(L>R) return 0;
	if(L<=t[root].l&&R>=t[root].r)
	{
		int y=t[root].sum;
		t[root].sum=d*(t[root].r-t[root].l+1);
		t[root].mark=d;return y;
	}
	if(t[root].mark!=-1) push_down(root);
	int mid=(t[root].l+t[root].r)>>1,sum=0;
	if(L<=mid) sum+=Change(t[root].ls,L,R,d);
	if(R>mid)  sum+=Change(t[root].rs,L,R,d);
	t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
	if(t[t[root].ls].mark==t[t[root].rs].mark) t[root].mark=t[t[root].ls].mark;
	else t[root].mark=-1;
	return sum;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d",&x);fa[i]=x;
		next[++tot]=st[x];st[x]=tot;to[tot]=i;
	}
	memset(son,-1,sizeof(son));
	tot=0;dfs1(0);dfs2(0);
	tot=1;Build(1,1,n);
	scanf("%d",&m);
	while(m--)
	{
		scanf("%s%d",s,&x);
		if(s[0]=='i')
		{
			ans=dep[x];f=top[x];
			while(f)
			{
				ans-=Change(1,fi[f],fi[x],1);
				x=fa[f];f=top[x];
			}
			ans-=Change(1,1,fi[x],1);
			printf("%d\n",ans);
		}
		else printf("%d\n",Change(1,fi[x],ed[x],0));
	}
}

好吧分开写是这样的，其实没啥区别了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int Sum(int root,int L,int R)
{
    if(L>R) return 0;
    if(L<=t[root].l&&R>=t[root].r) return t[root].sum;
    if(t[root].mark!=-1) push_down(root);
    int mid=(t[root].l+t[root].r)>>1,sum=0;
    if(L<=mid) sum+=Sum(t[root].ls,L,R);
    if(R>mid)  sum+=Sum(t[root].rs,L,R);
    return sum;
}
void Change(int root,int L,int R,int d)
{
    if(L>R) return;
    if(L<=t[root].l&&R>=t[root].r)
    {
        t[root].sum=d*(t[root].r-t[root].l+1);
        t[root].mark=d;return;
    }
    if(t[root].mark!=-1) push_down(root);
    int mid=(t[root].l+t[root].r)>>1;
    if(L<=mid) Change(t[root].ls,L,R,d);
    if(R>mid)  Change(t[root].rs,L,R,d);
    t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
    if(t[t[root].ls].mark==t[t[root].rs].mark) t[root].mark=t[t[root].ls].mark;
    else t[root].mark=-1;
}

4 树的查询（qtree）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<iostream>
#include<cstdio>
using namespace std;
const int N=10005;
int n,x,y,z,tot,ans,f1,f2;
int siz[N],dep[N],top[N],fa[N],son[N],w[N],a[N];
int next[N*2],st[N*2],to[N*2];
char s[10];
struct gggg{
	int x,y,z;
}g[N];
struct node{
	int l,r,ls,rs,maxx;
}t[N*2];
void dfs1(int x)
{
	siz[x]=1;dep[x]=dep[fa[x]]+1;
	for(int i=st[x];i;i=next[i])
	{
		int y=to[i];
		if(fa[x]==y) continue;
		fa[y]=x;dfs1(y);siz[x]+=siz[y];
		if(siz[y]>siz[son[x]]) son[x]=y;
	}
}
void dfs2(int x)
{
	w[x]=++tot;
	if(!son[x]) return;
	int y=son[x];top[y]=top[x];dfs2(y);
	for(int i=st[x];i;i=next[i])
	{
		y=to[i];
		if(fa[x]==y||son[x]==y) continue;
		top[y]=y;dfs2(y);
	}
}
void Build(int root,int L,int R)
{
	t[root].l=L;t[root].r=R;
	if(L==R)
	{
		t[root].maxx=a[L];return;
	}
	int mid=(L+R)>>1;
	t[root].ls=++tot;Build(tot,L,mid);
	t[root].rs=++tot;Build(tot,mid+1,R);
	t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
}
void change(int root,int pos,int d)
{
	if(t[root].l==t[root].r)
	{
		t[root].maxx=d;return;
	}
	int mid=(t[root].l+t[root].r)>>1;
	if(pos<=mid) change(t[root].ls,pos,d);
	else change(t[root].rs,pos,d);
	t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
}
int Max(int root,int L,int R)
{
	if(L<=t[root].l&&R>=t[root].r) return t[root].maxx;
	int mid=(t[root].l+t[root].r)>>1,maxx=-2147483647;
	if(L<=mid) maxx=Max(t[root].ls,L,R);
	if(R>mid)  maxx=max(maxx,Max(t[root].rs,L,R));
	return maxx;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].z);
		next[++tot]=st[g[i].x];st[g[i].x]=tot;to[tot]=g[i].y;
		next[++tot]=st[g[i].y];st[g[i].y]=tot;to[tot]=g[i].x;
	}
	tot=0;dfs1(1);top[1]=1;dfs2(1);
	for(int i=1;i<n;i++)
	{
		if(dep[g[i].x]<dep[g[i].y]) swap(g[i].x,g[i].y);
		a[w[g[i].x]]=g[i].z;
	}
	tot=1;Build(1,1,n);
	while(scanf("%s",s)&&s[0]!='D')
	{
		scanf("%d%d",&x,&y);
		if(s[0]=='C') change(1,w[g[x].x],y);
		else
		{
			ans=-2147483647;
			f1=top[x];f2=top[y];
			while(f1!=f2)
			{
				if(dep[f1]<dep[f2])  swap(x,y),swap(f1,f2);
				ans=max(ans,Max(1,w[f1],w[x]));
				x=fa[x];f1=top[x];f2=top[y];
			}
			if(w[x]>w[y]) swap(x,y);
			ans=max(ans,Max(1,w[x]+1,w[y]));
			printf("%d\n",ans);
		}
	}
}

5 种草地（grassplant）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100001;
int n,m,tot,ans,x,y,f1,f2;
int size[N],dep[N],fa[N],son[N],w[N],top[N];
int st[N*2],next[N*2],to[N*2];
char s[5];
struct node{
	int l,r,ls,rs,sum,mark;
}t[N*2];
void dfs1(int x)
{
	size[x]=1;dep[x]=dep[fa[x]]+1;
	for(int i=st[x];i;i=next[i])
	{
		int y=to[i];
		if(fa[x]==y) continue;
		fa[y]=x;dfs1(y);size[x]+=size[y];
		if(size[y]>size[son[x]]) son[x]=y;
	}
}
void dfs2(int x)
{
	w[x]=++tot;
	if(!son[x]) return;
	int y=son[x];top[y]=top[x];dfs2(y);
	for(int i=st[x];i;i=next[i])
	{
		y=to[i];
		if(fa[x]==y||son[x]==y) continue;
		top[y]=y;dfs2(y);
	}
}
void Build(int root,int L,int R)
{
	t[root].l=L;t[root].r=R;
	if(L==R) return;
	int mid=(L+R)>>1;
	t[root].ls=++tot; Build(tot,L,mid);
	t[root].rs=++tot; Build(tot,mid+1,R);
}
void push_down(int root)
{
	int L=t[root].ls,R=t[root].rs,ma=t[root].mark;t[root].mark=0;
	t[L].mark+=ma;t[L].sum+=(t[L].r-t[L].l+1)*ma;
	t[R].mark+=ma;t[R].sum+=(t[R].r-t[R].l+1)*ma;
}
void Add(int root,int L,int R)
{
	if(L<=t[root].l&&t[root].r<=R)
	{
		t[root].mark++;
		t[root].sum+=t[root].r-t[root].l+1;
		return;
	}
	if(t[root].mark) push_down(root);
	int mid=(t[root].l+t[root].r)>>1;
	if(L<=mid) Add(t[root].ls,L,R);
	if(R>mid)  Add(t[root].rs,L,R);
}
int Sum(int root,int L,int R)
{
	if(L<=t[root].l&&t[root].r<=R) return t[root].sum;
	if(t[root].mark) push_down(root);
	int mid=(t[root].l+t[root].r)>>1,sum=0;
	if(L<=mid) sum+=Sum(t[root].ls,L,R);
	if(R>mid)  sum+=Sum(t[root].rs,L,R);
	return sum;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		next[++tot]=st[x];st[x]=tot;to[tot]=y;
		next[++tot]=st[y];st[y]=tot;to[tot]=x;
	}
	tot=0;dfs1(1);top[1]=1;dfs2(1);
	tot=1;Build(1,1,n);
	while(m--)
	{
		scanf("%s%d%d",s,&x,&y);
		if(s[0]=='P')
		{
			f1=top[x];f2=top[y];
			while(f1!=f2)
			{
				if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
				Add(1,w[f1],w[x]);x=fa[f1];
				f1=top[x];f2=top[y];
			}
			if(dep[x]>dep[y]) swap(x,y); 
			  Add(1,w[x]+1,w[y]);
		}
		else
		{
			ans=0;
			f1=top[x];f2=top[y];
			while(f1!=f2)
			{
				if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
				ans+=Sum(1,w[f1],w[x]);x=fa[f1];
				f1=top[x];f2=top[y];
			}
			if(dep[x]>dep[y]) swap(x,y); 
			  ans+=Sum(1,w[x]+1,w[y]);
			printf("%d\n",ans);
		}
	}
}

6 查询树（tree）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<iostream>
#include<cstdio>
using namespace std;
const int N=10001;
int n,tot,x,y,z,f1,f2,ans;
int size[N],dep[N],fa[N],son[N],w[N],top[N],val[N];
int next[N*2],st[N*2],to[N*2];
char s[5];
struct node{
	int x,y,z;
}a[N];
struct tree{
	int l,r,ls,rs,maxx,minn,mark;
}t[N*2];
void dfs1(int x)
{
	size[x]=1;dep[x]=dep[fa[x]]+1;
	for(int i=st[x];i;i=next[i])
	{
		int y=to[i];
		if(fa[x]==y) continue;
		fa[y]=x;dfs1(y);size[x]+=size[y];
		if(size[y]>size[son[x]]) son[x]=y;
	}
}
void dfs2(int x)
{
	w[x]=++tot;
	if(!son[x]) return;
	int y=son[x];top[y]=top[x];dfs2(y);
	for(int i=st[x];i;i=next[i])
	{
		y=to[i];
		if(fa[x]==y||son[x]==y) continue;
		top[y]=y;dfs2(y);
	}
}
void Build(int root,int L,int R)
{
	t[root].l=L;t[root].r=R;
	if(L==R)
	{
		t[root].maxx=t[root].minn=val[L];return;
	}
	int mid=(L+R)>>1;
	t[root].ls=++tot;Build(tot,L,mid);
	t[root].rs=++tot;Build(tot,mid+1,R);
	t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
	t[root].minn=min(t[t[root].ls].minn,t[t[root].rs].minn);
}
void push_down(int root)
{
	int L=t[root].ls,R=t[root].rs,x,y;
	t[root].mark=0;
	x=t[L].maxx;y=t[L].minn;t[L].maxx=-y;t[L].minn=-x;t[L].mark=1-t[L].mark;
	x=t[R].maxx;y=t[R].minn;t[R].maxx=-y;t[R].minn=-x;t[R].mark=1-t[R].mark;
}
void Change(int root,int pos,int val)
{
	if(t[root].l==t[root].r)
	{
		t[root].maxx=t[root].minn=val;return;
	}
	if(t[root].mark) push_down(root);
	int mid=(t[root].l+t[root].r)>>1;
	if(pos<=mid) Change(t[root].ls,pos,val);
	else Change(t[root].rs,pos,val);
	t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
	t[root].minn=min(t[t[root].ls].minn,t[t[root].rs].minn);
}
void Fan(int root,int L,int R)
{
	if(L<=t[root].l&&R>=t[root].r)
	{
		t[root].mark=1-t[root].mark;
		int x=t[root].maxx,y=t[root].minn;
		t[root].maxx=-y;t[root].minn=-x;
		return;
	}
	if(t[root].mark) push_down(root);
	int mid=(t[root].l+t[root].r)>>1;
	if(L<=mid) Fan(t[root].ls,L,R);
	if(R>mid)  Fan(t[root].rs,L,R);
	t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
	t[root].minn=min(t[t[root].ls].minn,t[t[root].rs].minn);
}
int Max(int root,int L,int R)
{
	if(L<=t[root].l&&R>=t[root].r) return t[root].maxx;
	if(t[root].mark) push_down(root);
	int mid=(t[root].l+t[root].r)>>1,maxx=-2147483647;
	if(L<=mid) maxx=Max(t[root].ls,L,R);
	if(R>mid)  maxx=max(maxx,Max(t[root].rs,L,R));
	return maxx;
}
int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);a[i].x=x;a[i].y=y;a[i].z=z;
		next[++tot]=st[x];st[x]=tot;to[tot]=y;
		next[++tot]=st[y];st[y]=tot;to[tot]=x;
	}
	tot=0;top[1]=1;dfs1(1);dfs2(1);
	for(int i=1;i<n;i++)
	{
		if(dep[a[i].x]<dep[a[i].y]) swap(a[i].x,a[i].y);
		val[w[a[i].x]]=a[i].z;
	}
	tot=1;Build(1,1,n);
	while(scanf("%s",s)&&s[0]!='D')
	{
		scanf("%d%d",&x,&y);
		if(s[0]=='C')  Change(1,w[a[x].x],y);
		else if(s[0]=='N')
		{
			if(x==y) continue;
			while((f1=top[x])!=(f2=top[y]))
			{
				if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
				Fan(1,w[f1],w[x]);
				x=fa[f1];
			}
			if(dep[x]>dep[y]) swap(x,y);
			Fan(1,w[x]+1,w[y]);
		}
		else
		{
			ans=-2147483647;
			while((f1=top[x])!=(f2=top[y]))
			{
				if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
				ans=max(ans,Max(1,w[f1],w[x]));
				x=fa[f1];
			}
			if(dep[x]>dep[y]) swap(x,y);
			ans=max(ans,Max(1,w[x]+1,w[y]));
			printf("%d\n",ans);
		}
	}
}
树链剖分