做了三四道树剖，这题算是技巧性较高的了。。
看了看其他大佬的题解，感觉有些难的地方根本就没解释啊，故写文以记之。
这题难点有二：
- 正常模板为点权，此题是边权
由于一个点有多个儿子，但只有一个父亲，易想到将原点权代替成与父亲的边权处理。1号节点边权为0。
既然对于边权维护硬核转换为点权，则在树链上反复跳的时候,LCA点的权值是不能取的，因为LCA维护的是与他父亲的边权，u与v的路径上并不经过。
此外的话对于操作C你在修改一条单边的时候，应当选择深度大的节点（只有深度大的节点维护的边权才是U,V间的边权），其中需要额外加一个判断。
- 线段树的懒标记下放
我们可以设$neg[o]$为o节点的区间每个数是否取反，对区间和直接取反，对最大值用最小值的相反数替代，最小值同理。
对于$neg[o]$就进行取反操作即可，这可以用异或计算实现，本蒟蒻直接用”$neg[o]=!neg[o]$”水过了。。
此外就是一些树剖基本操作啦，最后注意求最小值的时候初值不能为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
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
using namespace std;
struct ed{
int next,v,w;
}e[50000];
int tr[100000][3],neg[100000];
int n,m,xx,yy,x[40000],y[40000],w[40000],st,numb,fir[30000],a[30000];
int d[30000],size[30000],f[30000],wu[30000],top[33000],son[30000],id[30000];
string s;
void add(int x,int y,int w)
{
e[++st].v=x; e[st].next=fir[y]; e[fir[y]=st].w=w;
e[++st].v=y; e[st].next=fir[x]; e[fir[x]=st].w=w;
}
void dfs1(int u,int fa,int w)
{
d[u]=d[fa]+1; size[u]=1; f[u]=fa; wu[u]=w;
for (int i=fir[u],maxx=0;i;i=e[i].next)
{
int v=e[i].v,w=e[i].w; if (v==fa) continue;
dfs1(v,u,w); size[u]+=size[v];
if (size[v]>maxx) maxx=size[v],son[u]=v;
}
}
void dfs2(int u,int to,int w) //w-->u上面那条边权
//a[i]为第i个点上面的边权
{
// cout<<u<<" "<<to<<endl;
id[u]=++st; a[st]=w; top[u]=to;
if (!son[u]) return; dfs2(son[u],to,wu[son[u]]);
for (int i=fir[u];i;i=e[i].next)
{
int v=e[i].v; if (v==son[u]||v==f[u]) continue;
dfs2(v,v,e[i].w);
}
}
//~~~~
void pushup(int o)
{
tr[o][0]=tr[o*2][0]+tr[o*2+1][0];
tr[o][1]=max(tr[o*2][1],tr[o*2+1][1]);
tr[o][2]=min(tr[o*2][2],tr[o*2+1][2]);
}
void pushdown(int o,int l,int r)
{
int min1=tr[o*2][2],min2=tr[o*2+1][2];
int max1=tr[o*2][1],max2=tr[o*2+1][1];
tr[o*2][0]=-tr[o*2][0]; tr[o*2+1][0]=-tr[o*2+1][0];
tr[o*2][1]=-min1; tr[o*2+1][1]=-min2;
tr[o*2][2]=-max1; tr[o*2+1][2]=-max2;
neg[o*2]=(neg[o]+neg[o*2])%2; neg[o*2+1]=(neg[o]+neg[o*2+1])%2; neg[o]=0;
}
void build(int o,int l,int r)
{
if (l==r) {tr[o][0]=tr[o][1]=tr[o][2]=a[l];return;}
int mid=(l+r)/2;
build(o*2,l,mid); build(o*2+1,mid+1,r);
pushup(o);
}
void change(int o,int l,int r,int x,int w)
{
if (l==r&&l==x) {
tr[o][0]=tr[o][1]=tr[o][2]=w; return;
}
if (l>x||r<x) return;
int mid=(l+r)/2;
if (neg[o])
pushdown(o,l,r);
change(o*2,l,mid,x,w); change(o*2+1,mid+1,r,x,w);
pushup(o);
}
void negat(int o,int l,int r,int x,int y)
{
if (l>=x&&r<=y) {
int nmax=tr[o][1],nmin=tr[o][2];
tr[o][0]=-tr[o][0]; tr[o][1]=-nmin; tr[o][2]=-nmax; neg[o]=!neg[o]; return;
}
if (l>y||r<x) return;
int mid=(l+r)/2;
if (neg[o])
pushdown(o,l,r);
negat(o*2,l,mid,x,y); negat(o*2+1,mid+1,r,x,y);
pushup(o);
}
int sum(int o,int l,int r,int x,int y)
{
if (l>=x&&r<=y) return tr[o][0];
if (l>y||r<x) return 0;
int mid=(l+r)/2;
if (neg[o])
pushdown(o,l,r);
return sum(o*2,l,mid,x,y)+sum(o*2+1,mid+1,r,x,y);
}
int maa(int o,int l,int r,int x,int y)
{
if (l>=x&&r<=y) return tr[o][1];
if (l>y||r<x) return -INT_MAX/2;
int mid=(l+r)/2;
if (neg[o])
pushdown(o,l,r);
return max(maa(o*2,l,mid,x,y),maa(o*2+1,mid+1,r,x,y));
}
int mii(int o,int l,int r,int x,int y)
{
if (l>=x&&r<=y) return tr[o][2];
if (l>y||r<x) return INT_MAX/2;
int mid=(l+r)/2;
if (neg[o])
pushdown(o,l,r);
return min(mii(o*2,l,mid,x,y),mii(o*2+1,mid+1,r,x,y));
}
int query(int x,int y,int p)
{
int ans=0;
if (p==2) ans=-INT_MAX/2; if (p==3) ans=INT_MAX/2;
while (top[x]!=top[y])
{
if (d[top[x]]<d[top[y]]) swap(x,y);
if (p==1) ans+=sum(1,1,n,id[top[x]],id[x]);
if (p==2) ans=max(ans,maa(1,1,n,id[top[x]],id[x]));
if (p==3) ans=min(ans,mii(1,1,n,id[top[x]],id[x]));
x=f[top[x]];
}
if (d[x]>d[y]) swap(x,y);
if (p==2) ans=max(ans,maa(1,1,n,id[x]+1,id[y]));
if (p==3) ans=min(ans,mii(1,1,n,id[x]+1,id[y]));
//+1出去LCA的影响
return ans;
}
void add1(int x,int y)
{
while (top[x]!=top[y])
{
if (d[top[x]]<d[top[y]]) swap(x,y);
negat(1,1,n,id[top[x]],id[x]);
x=f[top[x]];
}
if (d[x]<d[y]) swap(x,y);
negat(1,1,n,id[y]+1,id[x]);
}
int main()
{
cin>>n;
for (int i=1;i<n;i++) cin>>x[i]>>y[i]>>w[i],x[i]++,y[i]++,
add(x[i],y[i],w[i]);
st=0; dfs1(1,0,0); dfs2(1,1,0); build(1,1,n);
cin>>m; int wb=0;
for (int i=1;i<=m;i++)
{
cin>>s;
if (s[0]=='C') cin>>numb>>wb,
change(1,1,n,id[(d[y[numb]]>d[x[numb]])?y[numb]:x[numb]],wb);
//选深度大那个点上面的边
else if (s[0]=='N') cin>>xx>>yy,xx++,yy++,add1(xx,yy);
else {
cin>>xx>>yy;
xx++,yy++;
if (s[0]=='S') cout<<query(xx,yy,1)<<endl;
if (s[1]=='A') cout<<query(xx,yy,2)<<endl;
if (s[1]=='I') cout<<query(xx,yy,3)<<endl;
}
}
return 0;
}