大致题意： 维护一棵树，支持两种操作：
P x y x到y路径上的每条边的值+1；
Q x y 询问x到y路径上所有边的值的和。
Input
第一行两个正整数，N，M表示点数和操作数；
接下来N-1行每行两个数表示一条边；
接下来M行表示M个操作，每行形如P x y或Q x y。
2≤N≤100,000，1≤M≤100,000。
Output
M行，对应相应询问的答案。
Sample Input
4 6
1 4
2 4
3 4
P 2 3
P 1 3
Q 3 4
P 1 4
Q 2 4
Q 1 4
Sample Output
2
1
2
/*
大致题意： 维护一棵树，支持两种操作：
P x y x到y路径上的每条边的值+1；
Q x y 询问x到y路径上所有边的值的和
*/
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100050;
int m;
int read()
{
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
struct segment_tree
{
int sum[maxn*8],lazy[maxn*8];
void updata(int p){sum[p]=sum[p<<1]+sum[p<<1|1];}
void add_tag(int p,int v)
{
lazy[p]+=v;
sum[p]+=v;
}
void pushdown(int p)
{
if(!lazy[p])return;
add_tag(p<<1,lazy[p]);
add_tag(p<<1|1,lazy[p]);
lazy[p]=0;
}
void add(int p,int l,int r,int x,int y)
{
if(x>y)return;
if(x<=l&&r<=y)
{
add_tag(p,1);
return;
}
int mid=(l+r)>>1;
pushdown(p);
if(x<=mid)
add(p<<1,l,mid,x,y);
if(y>mid)
add(p<<1|1,mid+1,r,x,y);
updata(p);
}
int query(int p,int l,int r,int x,int y)
{
if(x>y)return 0;
if(x<=l&&r<=y)
return sum[p];
int mid=(l+r)>>1,ls=0,rs=0;
pushdown(p);
if(x<=mid)
ls=query(p<<1,l,mid,x,y);
if(y>mid)
rs=query(p<<1|1,mid+1,r,x,y);
return ls+rs;
}
}ST;
struct Tree
{
int n,tot,cnt;
int pre[maxn*2],son[maxn*2],now[maxn];
int dep[maxn],fa[maxn],siz[maxn],wson[maxn],top[maxn],seg[maxn];
void add(int a,int b)
{
pre[++tot]=now[a];
now[a]=tot;
son[tot]=b;
}
void in()
{
n=read(),m=read();
for(int i=1;i<n;i++)
{
int x=read(),y=read();
add(x,y);
add(y,x);
}
}
void dfs(int faa,int u)
{
fa[u]=faa;
dep[u]=dep[faa]+1;
siz[u]=1;
for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if(v!=faa)
{
dfs(u,v);
siz[u]+=siz[v];
if(siz[wson[u]]<siz[v])wson[u]=v;
}
}
void base(int tp,int u) //树链剖分
{
top[u]=tp;
seg[u]=++cnt;
if(wson[u])
base(tp,wson[u]);
for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if(v!=fa[u]&&v!=wson[u])base(v,v);
}
void addedg(int a,int b) //a到b的路径上边都加1
{
while(top[a]!=top[b])
{
if(dep[top[a]]<dep[top[b]])
swap(a,b);
ST.add(1,1,n,seg[top[a]],seg[a]);
a=fa[top[a]];
}
if(dep[a]<dep[b])
swap(a,b);
ST.add(1,1,n,seg[b]+1,seg[a]);
//注意是对边操作,所以是seg[b]+1
}
void query(int a,int b)
{
int ans=0;
while(top[a]!=top[b])
{
if(dep[top[a]]<dep[top[b]])swap(a,b);
ans+=ST.query(1,1,n,seg[top[a]],seg[a]);
a=fa[top[a]];
}
if(dep[a]<dep[b])
swap(a,b);
ans+=ST.query(1,1,n,seg[b]+1,seg[a]);
printf("%d
",ans);
}
}CT;
void work()
{
for(int i=1;i<=m;i++)
{
char s[10];int x,y;
scanf("%s",s);
x=read(),y=read();
if(s[0]=='P') //路径上加1
CT.addedg(x,y);
else
CT.query(x,y);
}
}
int main()
{
CT.in();
CT.dfs(0,1);
CT.base(1,1);
work();
return 0;
}