题解
树剖，不过是边问题，所以把边问题改成边的下面那个点的问题。
处理的时候注意一下即可。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
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
struct Edge{
int v,_next;
};
Edge edge[200005];
int cnt=0,at[100005]={0};
int fa[100005],son[100005]={0},siz[100005],top[100005],
depth[100005],pos[100005],fp[100005],val[100005];
int S,nows=0,n,m,_a,_b,C[400005];
int lowbit(int x){
return x&(-x);
}
void update(int k,int v){
while(k<=S)C[k]+=v,k+=lowbit(k);
}
int query(int r){
int res=0;
while(r)res+=C[r],r-=lowbit(r);
return res;
}
void addedge(int _u,int _v){
edge[++cnt].v=_v,
edge[cnt]._next=at[_u],
at[_u]=cnt;
}
void dfs1(int x,int par,int d){
depth[x]=d,fa[x]=par,siz[x]=1;
for(int i=at[x];i;i=edge[i]._next){
if(edge[i].v==par)continue;
int _v=edge[i].v;
dfs1(_v,x,d+1);
siz[x]+=siz[_v];
if(!son[x]||siz[_v]>siz[son[x]])
son[x]=_v;
}
}
void dfs2(int x,int tp){
top[x]=tp,pos[x]=++nows,fp[nows]=x;
if(!son[x])return;
dfs2(son[x],tp);
for(int i=at[x];i;i=edge[i]._next)
if(edge[i].v!=fa[x]&&edge[i].v!=son[x])
dfs2(edge[i].v,edge[i].v);
}
void update_tr(int u,int v){
while(top[u]!=top[v]){
if(depth[top[u]]<depth[top[v]])
swap(u,v);
update(pos[top[u]],1);
update(pos[u]+1,-1);
u=fa[top[u]];
}
if(depth[u]<depth[v])swap(u,v);
if(u==v)return ;
v=son[v];
update(pos[u]+1,-1);
update(pos[v],1);
}
int query_tr(int u,int v){
if(depth[u]<depth[v])swap(u,v);
return query(pos[u]);
}
void init(){
n=read(),m=read();
for(S=1;S<=n;S<<=1);
int u,v;
for(int i=1;i<n;i++){
u=read(),v=read();
addedge(u,v),addedge(v,u);
}
dfs1(1,0,1);
dfs2(1,1);
}
void solve(){
char ord[3];
int x,y;
while(m--){
scanf("%s%d%d",ord,&x,&y);
if(ord[0]=='P')update_tr(x,y);
else printf("%d\n",query_tr(x,y));
}
}
int main(){
init();
solve();
return 0;
}