图很丑。明显的树链剖分，需要的操作只有区间修改和区间查询。不过这里是边权，我们怎么把它转成点权呢？对于E(u,v)，我们选其深度大的节点，把边权扔给它。因为这是树，所以每个点只有一个父亲，所以每个边权都可以唯一地、不重复地转移到点上去(除了根节点)。但是做区间操作时就要注意一下，区间两边端点的LCA的权值是不可以用的。
这么简单的模板题就直接放代码了：
#include<iostream> #include<cstring> #include<cstdio> #define maxn 1000001 #define maxm 1000001 using namespace std; struct edge{ int to,next; edge(){} edge(const int &_to,const int &_next){ to=_to,next=_next; } }e[maxn<<1]; int head[maxn],k; struct node{ int l,r,c,f; }t[maxn<<2]; int size[maxn],son[maxn],fa[maxn],dep[maxn]; int dfn[maxn],id[maxn],top[maxn],tot; int n,m; inline int read(){ register int x(0); register char c(getchar()); while(c<'0'||'9'<c) c=getchar(); while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x; } inline void add(const int &u,const int &v){ e[k]=edge(v,head[u]); head[u]=k++; } void dfs_getson(int u){ size[u]=1; for(register int i=head[u];~i;i=e[i].next){ int v=e[i].to; if(v==fa[u]) continue; fa[v]=u,dep[v]=dep[u]+1; dfs_getson(v); size[u]+=size[v]; if(size[v]>size[son[u]]) son[u]=v; } } void dfs_rewrite(int u,int tp){ top[u]=tp,dfn[u]=++tot,id[tot]=u; if(son[u]) dfs_rewrite(son[u],tp); for(register int i=head[u];~i;i=e[i].next){ int v=e[i].to; if(v!=son[u]&&v!=fa[u]) dfs_rewrite(v,v); } } void build(int d,int l,int r){ t[d].l=l,t[d].r=r; if(l==r) return; int mid=(l+r)>>1; build(d<<1,l,mid),build(d<<1|1,mid+1,r); } inline void down(const int &d){ t[d<<1].c+=t[d].f*(t[d<<1].r-t[d<<1].l+1),t[d<<1].f+=t[d].f; t[d<<1|1].c+=t[d].f*(t[d<<1|1].r-t[d<<1|1].l+1),t[d<<1|1].f+=t[d].f; t[d].f=0; } void change(int d,const int &l,const int &r){ if(l<=t[d].l&&t[d].r<=r){ t[d].c+=t[d].r-t[d].l+1,t[d].f++; return; } if(t[d].f) down(d); int mid=(t[d].l+t[d].r)>>1; if(l<=mid) change(d<<1,l,r); if(r>mid) change(d<<1|1,l,r); t[d].c=t[d<<1].c+t[d<<1|1].c; } inline void change_path(){ int u=read(),v=read(); while(top[u]!=top[v]){ if(dep[top[u]]>dep[top[v]]) swap(u,v); change(1,dfn[top[v]],dfn[v]); v=fa[top[v]]; } if(dep[u]>dep[v]) swap(u,v); change(1,dfn[u]+1,dfn[v]);//加1是因为不能用LCA的权值 } int getsum(int d,const int &l,const int &r){ if(l<=t[d].l&&t[d].r<=r) return t[d].c; if(t[d].f) down(d); int mid=(t[d].l+t[d].r)>>1,ans=0; if(l<=mid) ans+=getsum(d<<1,l,r); if(r>mid) ans+=getsum(d<<1|1,l,r); return ans; } inline void getsum_path(){ int u=read(),v=read(),ans=0; while(top[u]!=top[v]){ if(dep[top[u]]>dep[top[v]]) swap(u,v); ans+=getsum(1,dfn[top[v]],dfn[v]); v=fa[top[v]]; } if(dep[u]>dep[v]) swap(u,v); ans+=getsum(1,dfn[u]+1,dfn[v]);//加1是因为不能用LCA的权值 printf("%d ",ans); } int main(){ memset(head,-1,sizeof head); n=read(),m=read(); int u,v; for(register int i=1;i<n;i++){ u=read(),v=read(); add(u,v),add(v,u); } dfs_getson(1); dfs_rewrite(1,1); build(1,1,tot); char op; for(register int i=1;i<=m;i++){ scanf("%s",&op); if(op=='P') change_path(); else getsum_path(); } return 0; }