@[Ptilopsis_w](/user/239167)
by Weight_of_the_Soul @ 2022-09-28 22:39:48
建议remake(
by Ptilopsis_w @ 2022-09-29 05:44:41
~~初始边权均为 0~~
by C_liar @ 2022-09-29 07:35:04
还有建树时，`dat(p) = a[l]` 是不对的，应该选(`dfn` 对应的节点的编号)的权值，个人习惯用 `id` 数组表示。
线段树上的节点相当于 `dfn` 值，直接这样会出问题（~~曾经因为这个wa了好多题~~），要写成 `dat(p) = a[id[l]]`。
by C_liar @ 2022-09-29 07:42:44
(哦，你用 `rk` 数组表示了
不管怎样吧，改好了。
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int rd() {
int x = 0, w = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') w = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = getchar();
}
return x * w;
}
const int N = 1e5 + 5;
int n, m;
struct Graph {
int v, nxt;
}e[N << 1];
int lk[N], ltp;
int dfn[N], son[N], fa[N], siz[N], dep[N];
int rk[N], cnt;
int top[N];
int a[N];
void ins(int u, int v) {
e[++ltp] = (Graph) {v, lk[u]};
lk[u] = ltp;
}
void dfs1(int u) {
siz[u] = 1;
son[u] = -1;
for(int i = lk[u]; i; i = e[i].nxt) {
int v = e[i].v;
if(!dep[v]) {
dep[v] = dep[u] + 1;
fa[v] = u;
a[v] = 0;/**/
dfs1(v);
siz[u] += siz[v];
if(son[u] == -1 || siz[son[u]] < siz[v])
son[u] = v;
}
}
}
void dfs2(int u, int t) {
top[u] = t;
++cnt;
dfn[u] = cnt;
rk[cnt] = u;
if(son[u] == -1) return ;
dfs2(son[u], t);
for(int i = lk[u]; i; i = e[i].nxt) {
int v = e[i].v;
if(v != son[u] && v != fa[u])
dfs2(v, v);
}
}
struct Tree {
int l, r;
int dat, tag;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define dat(x) tr[x].dat
#define tag(x) tr[x].tag
#define ls (p << 1)
#define rs (ls | 1)
} tr[N << 3];
void build(int p, int l, int r) {
l(p) = l, r(p) = r;
if(l == r) {
dat(p) = a[rk[l]];/**/
return ;
}
int mid = (r - l) / 2 + l;
build(ls, l, mid), build(rs, mid + 1, r);
dat(p) = dat(ls) + dat(rs);
}
void spr(int p) {
if(tag(p) != 0) {
tag(ls) += tag(p);
tag(rs) += tag(p);
dat(ls) += tag(p) * (r(ls) - l(ls) + 1);
dat(rs) += tag(p) * (r(rs) - l(rs) + 1);
tag(p) = 0;
}
}
void change(int p, int l, int r, int del) {
if(l <= l(p) && r >= r(p)) {
dat(p) += del * (r(p) - l(p) + 1);
tag(p) += del;
return ;
}
spr(p);
int mid = (r(p) - l(p)) / 2 + l(p);
if(l <= mid) change(ls, l, r, del);
if(r > mid) change(rs, l, r, del);
dat(p) = dat(ls) + dat(rs);
}
int ask(int p, int l, int r) {
if(l <= l(p) && r >= r(p)) return dat(p);
spr(p);
int res = 0;
int mid = (r(p) - l(p)) / 2 + l(p);
if(l <= mid) res += ask(ls, l, r);
if(r > mid) res += ask(rs, l, r);
dat(p) = dat(ls) + dat(rs);
return res;
}
int main() {
n = rd(), m = rd();
for(int i = 1; i < n; ++i) {
int u = rd(), v = rd();
ins(u, v);
ins(v, u);
}
dep[1] = 1;
dfs1(1);
dfs2(1, 1);
build(1, 1, n);
while(m--) {
char opt;
cin >> opt;
int u = rd(), v = rd();
if(opt == 'P') {
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]]) swap(u, v);
change(1, dfn[top[u]], dfn[u], 1);
u = fa[top[u]];
}
if(dep[u] > dep[v]) swap(u, v);
change(1, dfn[u], dfn[v], 1);
change(1, dfn[u], dfn[u], -1);
} else {
int ans = 0;
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]]) swap(u, v);
ans += ask(1, dfn[top[u]], dfn[u]);
u = fa[top[u]];
}
if(dep[u] > dep[v]) swap(u, v);
ans += ask(1, dfn[u], dfn[v]);
ans -= ask(1, dfn[u], dfn[u]);
/*直接这样就行：ask(1, dfn[u]+1, dfn[v]) 不过线段树代码中要处理一些 l>r 的情况*/
printf("%d\n", ans);
}
}
return 0;
}
```
by C_liar @ 2022-09-29 07:47:10
QwQ,%东区大佬
by C_liar @ 2022-09-29 07:48:46
@[C_liar](/user/663681) tql，thx
by Weight_of_the_Soul @ 2022-09-29 22:04:24