肯定先无脑树链剖分，然后线段树维护一段区间不同个数，再维护一个左右端点的费用。
线段树更新，pushDown，pushUp的时候要注意考虑链接位置的费用是否相同
还有就是树链剖分操作的时候，维护上一个更新的位置的费用。
总之就是出现区间合并，就考虑总数是否要减一
好想不好写
//场上根本写不完啊
/*--------------------------------------------------------------------------------------*/ #include <algorithm>
#include <iostream>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map> //debug function for a N*M array
#define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++)\
{for(int j=;j<(M);j++){\
printf("%d",G[i][j]);}printf("\n");}
//debug function for int,float,double,etc.
#define debug_var(X) cout<<#X"="<<X<<endl;
#define LL long long
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
/*--------------------------------------------------------------------------------------*/
using namespace std; int N,M,T;
const int maxn = 2e5+; struct Edge{
int x,y,val;
}e[maxn]; vector <int> G[maxn]; int val[maxn],dep[maxn],siz[maxn],top[maxn],id[maxn],son[maxn],fa[maxn];
int topw; void init()
{
for(int i=;i<maxn;i++) G[i].clear();
topw = ;
} void dfs_1(int u,int f,int d)
{
fa[u] = f;
son[u] = ;
siz[u] = ;
dep[u] = d;
for(int i=;i<G[u].size();i++) if(G[u][i] != f)
{
dfs_1(G[u][i],u,d+);
siz[u] += siz[G[u][i]];
if(siz[son[u]] < siz[G[u][i] ])
{
son[u] = G[u][i];
}
}
} void dfs_2(int u,int tp)
{
top[u] = tp;
id[u] = ++topw;
if(son[u]) dfs_2(son[u],tp);
for(int i=;i<G[u].size();i++) if(G[u][i]!=fa[u] && G[u][i] != son[u] )
{
dfs_2(G[u][i],G[u][i]);
}
} void debug()
{
for(int i=;i<=N;i++)
{
printf("%d siz:%d son:%d dep:%d fa:%d ",i,siz[i],son[i],dep[i],fa[i]);
printf("top:%d id:%d\n",top[i],id[i]);
}
return ;
} /*-----------------------------------*/
#define lson(x) (x<<1)
#define rson(x) (x<<1|1) struct SegmentTree{
int l,r;
int lazy;
int num,lcost,rcost;
}segtree[*maxn]; void pushUp(int x)
{
segtree[x].num = segtree[lson(x)].num + segtree[rson(x)].num - (segtree[lson(x)].rcost==segtree[rson(x)].lcost? : );
segtree[x].lcost = segtree[lson(x)].lcost;
segtree[x].rcost = segtree[rson(x)].rcost;
//printf("x:%d [%d,%d] num:%d\n",x,segtree[x].l,segtree[x].r,segtree[x].num);
//printf("lcost:%d rcost:%d\n",segtree[x].lcost,segtree[x].rcost);
//printf("l->rcost:%d r->lcost:%d\n",segtree[lson(x)].rcost,segtree[rson(x)].lcost);
} void pushDown(int x)
{
if(segtree[x].lazy != -)
{
segtree[lson(x)].lcost = segtree[lson(x)].rcost = segtree[x].lazy;
segtree[rson(x)].lcost = segtree[rson(x)].rcost = segtree[x].lazy;
segtree[lson(x)].num = segtree[rson(x)].num = ;
segtree[lson(x)].lazy = segtree[rson(x)].lazy = segtree[x].lazy;
segtree[x].lazy = -;
}
} void Build(int l,int r,int x)
{
segtree[x].l = l;
segtree[x].r = r;
segtree[x].lazy = -;
if(l == r)
{
segtree[x].num = ;
segtree[x].lcost = segtree[x].rcost = val[l];
return ;
}
int mid = (l+r)>>;
Build(l,mid,lson(x));
Build(mid+,r,rson(x));
pushUp(x);
} void update(int x,int L,int R,int cost)
{
if(segtree[x].l >= L && segtree[x].r <= R)
{
segtree[x].lcost = segtree[x].rcost = cost;
segtree[x].num = ;
segtree[x].lazy = cost;
return ;
}
pushDown(x);
int mid = (segtree[x].l + segtree[x].r) >> ;
if(L <= mid) update(lson(x),L,R,cost);
if(R > mid) update(rson(x),L,R,cost);
pushUp(x);
return ;
} int query(int x,int L,int R)
{
if(segtree[x].l >= L && segtree[x].r <= R)
{
return segtree[x].num;
}
pushDown(x);
int mid = (segtree[x].l + segtree[x].r) >> ;
int ans = ; if(R <= mid) ans = query(lson(x),L,R);
else if(L > mid) ans = query(rson(x),L,R);
else ans = query(lson(x),L,R) + query(rson(x),L,R) - (segtree[lson(x)].rcost==segtree[rson(x)].lcost ? : ) ;
pushUp(x);
return ans;
} int query_edge(int x,int pos)
{
if(segtree[x].l == segtree[x].r)
{
return segtree[x].lcost;
}
pushDown(x);
int res = ;
int mid = (segtree[x].l + segtree[x].r) >> ;
if(pos <= mid) res = query_edge(lson(x),pos);
else res = query_edge(rson(x),pos);
pushUp(x);
return res ;
} int Find(int u,int v)
{
int ans = ,fu = top[u],fv = top[v];
int last_u=- , last_v = -;
int last_u_color,last_v_color;
//printf("%d->%d\n",u,v); while(fu != fv)
{
if(dep[fu] < dep[fv])
{
swap(fu,fv);swap(u,v);
swap(last_u,last_v);
swap(last_u_color,last_v_color);
} //printf("query:[%d,%d] %d->%d ",id[fu],id[u],u,fu);
//printf("%d\n",query(1,id[fu],id[u]));
ans += query(,id[fu],id[u]);
if(last_u == -)
{
last_u = fu;
last_u_color = query_edge(,id[fu]);
}
else
{
if(last_u != - && fa[last_u] == u)
{
//printf("u sub:%d\n",(last_u_color==query_edge(1,id[u]) ? 1 : 0));
ans -= (last_u_color==query_edge(,id[u]) ? : );
last_u = fu;
last_u_color = query_edge(,id[fu]);
}
}
u = fa[fu];
fu = top[u];
}
if(u == v)
{
if(last_u != - && last_v != - && last_u_color==last_v_color) ans -= ;
return ans;
}
if(dep[u] < dep[v])
{
swap(u,v);
swap(last_u,last_v);
swap(last_u_color,last_v_color);
}
//printf("query:[%d,%d] %d->%d ",id[son[v]],id[u],u,son[v]);
ans += query(,id[son[v] ],id[u]);
//printf("%d*\n",query(1,id[son[v]],id[u])); //printf("last_u:%d last_v:%d\n",last_u,last_v);
if(last_u != - && fa[last_u] == u)
{
//printf("u sub:%d last_u_color:%d u_color:%d\n",(last_u_color==query_edge(1,id[u]) ? 1 : 0),last_u_color,query_edge(1,id[u]));
ans -= (last_u_color==query_edge(,id[u]) ? : );
last_u = fu;
last_u_color = query_edge(,id[u]);
} if(last_v != - && fa[last_v] == v)
{
//printf("v sub:%d last_v_color:%d son[v]_color:%d\n",(last_v_color==query_edge(1,id[son[v]]) ? 1 : 0),last_v_color,query_edge(1,id[son[v]] ));
ans -= (last_v_color==query_edge(,id[son[v]]) ? : );
last_v = fv;
last_v_color = query_edge(,id[son[v]]);
} return ans;
} void Change(int u,int v,int cost)
{
int fu = top[u],fv = top[v];
//printf("%d->%d\n",u,v);
while(fu != fv)
{
if(dep[fu] < dep[fv])
{
swap(fu,fv);swap(u,v);
}
//printf("change:[%d,%d] %d->%d %d\n",id[fu],id[u],u,fu,cost);
update(,id[fu],id[u],cost);
u = fa[fu];
fu = top[u];
}
if(u == v) return ;
if(dep[u] < dep[v]) swap(u,v);
//printf("change:[%d,%d] %d->%d %d\n",id[son[v]],id[u],u,son[u],cost);
update(,id[son[v]],id[u],cost);
return ;
} int main()
{
//freopen("input","r",stdin);
while(~scanf("%d%d",&N,&M))
{
init();
int u,v,w;
for(int i=;i<N;i++)
{
scanf("%d%d%d",&u,&v,&w);
e[i].x = u;e[i].y = v;e[i].val = w;
G[u].push_back(v);
G[v].push_back(u);
}
topw = ;
dfs_1(,,);
dfs_2(,);
//debug();
for(int i=;i<N;i++)
{
if(dep[e[i].x] < dep[e[i].y]) swap(e[i].x,e[i].y);
val[id[e[i].x]] = e[i].val;
} Build(,topw,);
char op[];
//printf("-----------------\n");
for(int i=;i<M;i++)
{
scanf("%s",op);
if(op[] == 'Q')
{
scanf("%d%d",&u,&v);
printf("%d\n",Find(u,v));
}
else
{
scanf("%d%d%d",&u,&v,&w);
Change(u,v,w);
}
//puts("");
}
}
}