在另一道题目的基础上的改编题目，只不过把点权改成了边权，因为在边上，所以在合并区间时候注意lca点处的答案不需要合并。写法很多，当时这个check一直没想明白，wa了9发，到最后算是绝杀了吧。树链剖分题目还是完全理解概念以后再碰吧，否则会wa的很惨的。不过这个算法算是很精髓的了，可以解决大部分树链问题。
//#include <bits\stdc++.h> //#pragma comment(linker,"/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <iostream> #include <cstdlib> #include <vector> #include <stack> #include <queue> #include <map> #include <set> #include <ctime> #include <cmath> #include <algorithm> #include <bitset> #define sqr(x) ((x)*(x)) #define lson (p<<1) #define rson (lson | 1) #define EPS 1e-10 #define PII pair<int,int> #define PLI pair<LL,int> #define PLL pair<LL,LL> #define PIL pair<int,LL> #define mk(x,y) make_pair(x,y) #define lowbit(x) (x&(-x)) #define FRfreopen("in.txt","r",stdin) #define FWfreopen("out.txt","w",stdout) using namespace std; template <class T> inline voidread(T &x){char c = getchar(); x =0;while(!isdigit(c))c = getchar();while(isdigit(c)){x=x*10+ c-'0';c = getchar();}} template <class T> inline voidrd(T &res) {static char ch; bool sgn =false;while (ch = getchar(), ch < '0' ||ch > '9') if (ch == '-') sgn = true; res = ch - 48;while (ch = getchar(),ch >= '0' && ch <= '9') res =res * 10 + ch - 48; res = sgn ? -res: res;} template <class T> void Out(T a) { if(a < 0){putchar('-');a= -a;}if(a >= 10)Out(a / 10);putchar(a% 10 + '0'); } typedef long long LL; #define INT __int64 #define L(x) (x * 2) #define R(x) (x * 2 + 1) const int MX= 1e5+10; const int N= 1e5+10; const int oo= -0x3f3f3f3f; int n ,m,idx ,num ; int head[MX],ti[MX] ,top[MX] ,dep[MX] ,siz[MX],son[MX] ,father[MX] ,g[MX] ; struct Edge { int v ,next; }E[MX*2]; void addedge(intu ,int v) { E[num].v= v ; E[num].next = head[u] ;head[u] = num++ ; E[num].v= u ; E[num].next = head[v] ;head[v] = num++ ; } voiddfs_find(int u ,int fa) { dep[u] = dep[fa] + 1 ; siz[u] = 1 ; son[u] = 0 ; father[u] = fa ; for(int i = head[u] ;i!= -1 ;i = E[i].next) { int v = E[i].v ; if(v == fa) continue ; dfs_find(v ,u) ; siz[u] += siz[v]; if(siz[son[u]] < siz[v]) son[u] = v ; } } voiddfs_time(int u ,int fa) { ti[u] = idx++; top[u] = fa ; if(son[u]) dfs_time(son[u] ,top[u]); for(int i = head[u] ;i!= -1 ;i = E[i].next) { int v = E[i].v ; if(v == father[u] || v== son[u]) continue; dfs_time(v ,v) ; } } struct node { int le ,rt ,lc ,rc ,num,add ; }T[MX<<2]; void build(intx ,int le ,int rt) { T[x].le= le ; T[x].rt = rt ; T[x].lc= T[x].rc = T[x].add = oo; T[x].num= 0 ; if(le == rt) return ; int Mid = (le + rt)>>1; build(L(x) ,le ,Mid) ; build(R(x) ,Mid + 1 ,rt) ; } voidpush_down(int x) { if(T[x].add != oo) { T[L(x)].lc = T[L(x)].rc= T[L(x)].add = T[x].add ;T[L(x)].num = 1 ; T[R(x)].lc = T[R(x)].rc= T[R(x)].add = T[x].add ;T[R(x)].num = 1 ; T[x].add = oo; } } void push_up(intx) { T[x].num= T[L(x)].num + T[R(x)].num; if(T[L(x)].rc ==T[R(x)].lc) T[x].num -- ; T[x].lc= T[L(x)].lc ; T[x].rc = T[R(x)].rc; } void update(intx ,int le ,int rt ,int w) { if(T[x].le == le&& T[x].rt == rt) { T[x].add = w ; T[x].lc =w ; T[x].rc = w ; T[x].num= 1; return ; } push_down(x); int Mid = (T[x].le +T[x].rt)>>1; if(le > Mid) update(R(x) ,le ,rt,w) ; else if(rt <= Mid) update(L(x) ,le ,rt,w) ; else { update(L(x) ,le ,Mid ,w) ; update(R(x) ,Mid+1 ,rt ,w); } push_up(x) ; } int Query(intx ,int le ,int rt) { if(T[x].le == le&& T[x].rt == rt) return T[x].num; int Mid = (T[x].le +T[x].rt)>>1 ; push_down(x) ; if(le > Mid) return Query(R(x) ,le ,rt) ; else if(rt <= Mid) return Query(L(x) ,le ,rt); else { int mx = 0 ; if(T[L(x)].rc ==T[R(x)].lc) mx = -1; return Query(L(x) ,le ,Mid) + Query(R(x),Mid+1 ,rt) + mx ; } push_up(x) ; } intQuerynode(int x ,int pos) { if(T[x].le == T[x].rt)return T[x].lc ; int Mid = (T[x].le +T[x].rt)>>1 ; push_down(x) ; if(pos <= Mid) return Querynode(L(x) ,pos) ; else return Querynode(R(x),pos) ; push_up(x) ; } void LCAC(intu ,int v ,int w) { while(top[u] != top[v]) { if(dep[top[u]] < dep[top[v]])swap(u ,v) ; update(1 ,ti[top[u]],ti[u] ,w) ; u = father[top[u]] ; } if(u == v) return; if(dep[u] > dep[v])swap(u ,v) ; update(1 ,ti[son[u]] ,ti[v],w) ; } int LCAQ(intu ,int v) { if(u == v) return 0; int ans = 0; while(top[u] != top[v]) { if(father[u] == father[v]) { ans += Query(1 ,ti[u] ,ti[u])+ Query(1 ,ti[v] ,ti[v]); if(Querynode(1,ti[u]) == Querynode(1 ,ti[v] ))ans--; returnans; } if(dep[top[u]] < dep[top[v]])swap(u ,v) ; ans += Query(1 ,ti[top[u]] ,ti[u]); int x = father[top[u]]; if(top[x] == top[v]) { if(dep[x]<= dep[v]) { if(x== v) return ans; if(Querynode(1 ,ti[top[u]]) == Querynode(1,ti[ son[x] ] ) ) ans--; u = father[top[u]]; break; } } if(Querynode(1 ,ti[top[u]])== Querynode(1 ,ti[father[top[u]]]))ans--; u = father[top[u]] ; } if(u == v) return ans; if(dep[u] > dep[v])swap(u ,v) ; ans += Query(1 ,ti[son[u]] ,ti[v]); return ans ; } struct rp { int x,y,w; }f[N]; char s[110]; int main() { while(~scanf("%d%d",&n,&m)) { int u,v,w ; num = 0; memset(head ,-1 ,sizeof(head)) ; for(int i = 1 ;i < n; ++i) { scanf("%d%d%d" ,&u ,&v, &w) ; addedge(u ,v); f[i].x = u; f[i].y = v; f[i].w = w; } dep[1] = siz[0] = 0 ; dfs_find(1,1); father[1] = 0; idx = 1; dfs_time(1,1); build(1 ,1 ,idx); for(int i = 1 ;i < n; ++i) { if(dep[f[i].x]>dep[f[i].y]) swap(f[i].x,f[i].y); update(1 ,ti[f[i].y],ti[f[i].y] ,f[i].w) ; } for(int i = 0 ;i < m; ++i) { scanf("%s",s); scanf("%d%d",&u ,&v); if(s[0]== 'C') { scanf("%d",&w); if(u>n|| v>n) continue; LCAC(u,v,w); } elseprintf("%d\n",(u>n || v>n)? 0 : LCAQ(u,v) ); } } return 0 ; } /* 9 3 1 2 2 2 3 1 1 7 2 1 4 2 3 5 2 3 6 1 5 8 2 5 9 3 Query 1 8 Change 2 6 3 Query 1 6 */
