题目描述
Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1 bidirectional roads, such that there is exactly one path between any two pastures. Bessie, a cow who loves her grazing time, often complains about how there is no grass on the roads between pastures. Farmer John loves Bessie very much, and today he is finally going to plant grass on the roads. He will do so using a procedure consisting of M steps (1 <= M <= 100,000).
At each step one of two things will happen:
-
FJ will choose two pastures, and plant a patch of grass along each road in between the two pastures, or,
-
Bessie will ask about how many patches of grass on a particular road, and Farmer John must answer her question.
Farmer John is a very poor counter -- help him answer Bessie's questions!
给出一棵n个节点的树，有m个操作，操作为将一条路径上的边权加一或询问某条边的权值。
输入输出格式
输入格式：* Line 1: Two space-separated integers N and M
* Lines 2..N: Two space-separated integers describing the endpoints of a road.
* Lines N+1..N+M: Line i+1 describes step i. The first character of the line is either P or Q, which describes whether or not FJ is planting grass or simply querying. This is followed by two space-separated integers A_i and B_i (1 <= A_i, B_i <= N) which describe FJ's action or query.
输出格式：* Lines 1..???: Each line has the answer to a query, appearing in the same order as the queries appear in the input.
输入输出样例
输入样例#1： 复制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输出样例#1： 复制
2 1 2
【解题思路】
//树剖是在点上操作的，这道题是边
//那么怎么把边权转成点权呢？
//根据树的性质可以知道，一个点可以有多个儿子，但是只会有一个爸爸，
//所以我们可以把这个点和它爸爸之间的那条边的边权转移到这个点上来
//用这个点的点权来表示这条边的权值
//因为根节点没有爸爸，所以它不表示任何边权，点权为0
//但是我们怎么样才能不把两个点的公共祖先的权值算进去啊？
//node[fx].s+1? 不行，这是它的重儿子的位置
// 考虑一下，我们在Query或者Modify的时候，都是当x和y同时处于一条链了之后就break
//然后再把这条链加上，最近公共祖先不就是这条链的top嘛！
//所以，我们在while循环外边写node[x].s+1就可以不算上公共祖先了。
//但是也要注意，如果最后是条轻边，我们就要if特判一下，不能让他进线段树查询了
//因为如果是轻边的话，最后的那条链退化成了最近公共祖先这一个点，不能要！
【code】
1 // luogu-judger-enable-o2
2 #include <cstdio>
3 #include <algorithm>
4 using namespace std;
5 int n,a,b,q,x,y,tim,cnt,u,v;
6 int head[200005],nxt[200005],end[200005],s[200005],t[200005],d[200005],fa[200005];
7 int son[200005],sum[400005],add[400005],tree[200005],p[200005];
8 char c;
9 void Push(int u,int v){
10 cnt++;
11 nxt[cnt]=head[u];
12 head[u]=cnt;
13 end[cnt]=v;
14 return ;
15 }
16 inline void read(int &a){
17 a=0;
18 char ch;
19 while((ch=getchar())<48);
20 while(ch>47)
21 a=(a<<1)+(a<<3)+(ch^48),ch=getchar();
22 }
23 inline void swap(int &a,int &b){
24 int t;
25 t=a,a=b,b=t;
26 return ;
27 }
28 inline void Pushdown(int w,int l,int r){
29 add[w<<1]+=add[w];
30 add[w<<1|1]+=add[w];
31 sum[w<<1]+=add[w]*l;
32 sum[w<<1|1]+=add[w]*r;
33 add[w]=0;
34 }
35 inline int Update(int l,int r,int w){
36 if(l>b||a>r)
37 return 0;
38 if(a<=l&&r<=b)
39 return sum[w];
40 int m=(l+r)>>1;
41 if(add[w])
42 Pushdown(w,m-l+1,r-m);
43 return Update(l,m,w<<1)+Update(m+1,r,w<<1|1);
44 }
45 inline void Query(int l,int r,int w,int x){
46 if(l>b||a>r)
47 return;
48 if(a<=l&&r<=b){
49 sum[w]+=(r-l+1)*x;
50 add[w]+=x;
51 return;
52 }
53 int m=(l+r)>>1;
54 if(add[w])Pushdown(w,m-l+1,r-m);
55 Query(l,m,w<<1,x);
56 Query(m+1,r,w<<1|1,x);
57 sum[w]=sum[w<<1]+sum[w<<1|1];
58 }
59
60 inline void dfs1(int x){
61 s[x]=1;
62 for(int i=head[x];i;i=nxt[i])
63 if(end[i]!=fa[x]){
64 int v=end[i];
65 d[v]=d[x]+1;
66 fa[v]=x;
67 dfs1(v);
68 s[x]+=s[v];
69 if(s[v]>s[son[x]])
70 son[x]=v;
71 }
72 }
73
74 inline void dfs2(int x){
75 tree[x]=++tim;
76 if(!son[x])
77 return;
78 t[son[x]]=t[x];
79 dfs2(son[x]);
80 for(int i=head[x];i;i=nxt[i])
81 if(end[i]!=fa[x]&&end[i]!=son[x]){
82 t[end[i]]=end[i];
83 dfs2(end[i]);
84 }
85 }
86
87 inline void change(int x,int y){
88 while(t[x]!=t[y]){
89 if (d[t[x]]<d[t[y]])swap(x,y);
90 a=tree[t[x]];
91 b=tree[x];
92 Query(1,n,1,1);
93 x=fa[t[x]];
94 }
95 if(d[x]>d[y])swap(x,y);
96 a=tree[son[x]];
97 b=tree[y];
98 Query(1,n,1,1);
99 }
100
101 inline int lca(int x,int y){
102 int tmp=0;
103 while(t[x]!=t[y]){
104 if(d[t[x]]<d[t[y]])
105 swap(x,y);
106 a=tree[t[x]];
107 b=tree[x];
108 tmp+=Update(1,n,1);
109 x=fa[t[x]];
110 }
111 if(d[x]>d[y])swap(x,y);
112 a=tree[son[x]];
113 b=tree[y];
114 tmp+=Update(1,n,1);
115 return tmp;
116 }
117
118 int main(){
119 //freopen("grassplant.in","r",stdin);
120 //freopen("grassplant.out","w",stdout);
121 scanf("%d%d",&n,&q);
122 for(int i=1;i<n;i++){
123 read(u),read(v);
124 Push(u,v),Push(v,u);
125 }
126 dfs1(1);
127 t[1]=1;
128 dfs2(1);
129 while(q--){
130 c=getchar();
131 while(c!='P'&&c!='Q')
132 c=getchar();
133 read(x),read(y);
134 if(c=='P')change(x,y);
135 else printf("%d\n",lca(x,y));
136 }
137 return 0;
138 }