本题可以说是板题 P3384 的弱化版，只不过要改的变成了边权
边权很好处理，只需要将每个边的边权下放到两端点深度比较深的上面就好了（因为每个点连比它浅的节点必定只有一条边）。
那么就将模板改一下就好了
代码如下：
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int head[N], e_cnt;
int siz[N], son[N], fa[N], dep[N], id[N], cnt, top[N];
struct edge {
int to, nxt;
}e[N << 1];
void swap(int &a, int &b) {
a ^= b;
b ^= a;
a ^= b;
return ;
}
void add(int u, int v) {
e[++ e_cnt] = (edge){v, head[u]};
head[u] = e_cnt;
}
void dfs1(int sx, int ffa) {
fa[sx] = ffa;
dep[sx] = dep[ffa] + 1;
siz[sx] = 1;
int maxn = -1;
for (int i = head[sx];i;i = e[i].nxt) {
if (e[i].to == ffa) continue;
dfs1 (e[i].to, sx);
siz[sx] += siz[e[i].to];
if (siz[e[i].to] > maxn) {
maxn = e[i].to;
son[sx] = e[i].to;
}
}
return ;
}
void dfs2(int sx, int topf) {
id[sx] = ++ cnt;
top[sx] = topf;
if (son[sx] != 0)
dfs2 (son[sx], topf);
for (int i = head[sx];i;i = e[i].nxt) {
if (e[i].to == fa[sx] || e[i].to == son[sx]) continue;
dfs2 (e[i].to, e[i].to);
}
return ;
}
struct sgt {
int sum[N << 2], lz[N << 2];
void PushUp(int u) {
sum[u] = sum[u << 1] + sum[u << 1 | 1];
return ;
}
void PushDown(int u, int s) {
if (lz[u]) {
sum[u << 1] += lz[u] * (s - (s >> 1));
sum[u << 1 | 1] += lz[u] * (s >> 1);
lz[u << 1] += lz[u];
lz[u << 1 | 1] += lz[u];
lz[u] = 0;
}
return ;
}
void build(int u, int l, int r) {
if (l == r) {
sum[u] = 0;
return ;
}
int mid = l + r >> 1;
build (u << 1, l, mid);
build (u << 1 | 1, mid + 1, r);
PushUp (u);
}
void modify(int u, int l, int r, int L, int R, int k) {
if (L <= l && r <= R) {
sum[u] += (r - l + 1) * k;
lz[u] += k;
return ;
}
PushDown (u, r - l + 1);
int mid = l + r >> 1;
if (L <= mid)
modify (u << 1, l, mid, L, R, k);
if (mid < R)
modify (u << 1 | 1, mid + 1, r, L, R, k);
PushUp (u);
return ;
}
void change(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]])
swap (x, y);
modify (1, 1, n, id[top[y]], id[y], 1);
y = fa[top[y]];
}
if (dep[x] > dep[y])
swap (x, y);
modify (1, 1, n, id[x] + 1, id[y], 1);
return ;
}
int query(int u, int l, int r, int L, int R) {
if (L <= l && r <= R)
return sum[u];
int ans = 0, mid = l + r >> 1;
PushDown (u, r - l + 1);
if (L <= mid)
ans += query (u << 1, l, mid, L, R);
if (mid < R)
ans += query (u << 1 | 1, mid + 1, r, L, R);
return ans;
}
}tre;
int main() {
scanf ("%d%d", &n, &m);
for (int i = 1;i < n; ++ i) {
int u, v;
scanf ("%d%d", &u, &v);
add(u, v), add(v, u);
}
dfs1(1, 1);
dfs2(1, 1);
tre.build(1, 1, n);
while (m --) {
char opt;
scanf (" %c", &opt);
if (opt == 'P') {
int x, y;
scanf ("%d%d", &x, &y);
tre.change (x, y);
}
if (opt == 'Q') {
int x, y;
scanf ("%d%d", &x, &y);
if (dep[x] > dep[y])
printf ("%d\n", tre.query(1, 1, n, id[x], id[x]));
else printf ("%d\n", tre.query(1, 1, n, id[y], id[y]));
}
}
return 0;
}
轻松 A 掉了这道题目，但是线段树这么长，码着也怪累的，而且还不好调，再看题目我们惊奇地发现每次 Q 操作只找一条边，下放后就相当于只查询单点，那么区间修改，单点查询就可以用树状数组来替代线段树，所以就有了二代代码
#include <cstdio>
#define lowbit(x) (x) & (-x)
using namespace std;
const int N = 1e5 + 5;
int head[N], e_cnt;
int n, m;
int fa[N], siz[N], son[N], dep[N];
int id[N], cnt, top[N];
struct edge {
int nxt, to;
}e[N << 1];
void add(int u, int v) {
e[++e_cnt] = (edge){head[u], v};
head[u] = e_cnt;
}
void swap(int &a, int &b) {
a ^= b;
b ^= a;
a ^= b;
}
void dfs1(int sx, int ffa) {
fa[sx] = ffa;
siz[sx] = 1;
dep[sx] = dep[ffa] + 1;
int maxn = -1;
for (int i = head[sx];i;i = e[i].nxt) {
if (e[i].to == ffa) continue;
dfs1 (e[i].to, sx);
if (siz[e[i].to] > maxn) {
maxn = siz[e[i].to];
son[sx] = e[i].to;
}
siz[sx] += siz[e[i].to];
}
return ;
}
void dfs2(int sx, int topf) {
top[sx] = topf;
id[sx] = ++ cnt;
if (son[sx]) dfs2 (son[sx], topf);
for (int i = head[sx];i;i = e[i].nxt) {
if (e[i].to == fa[sx] || e[i].to == son[sx]) continue;
dfs2 (e[i].to, e[i].to);
}
return ;
}
int tre[N];
void modify(int x, int k) {
for (;x <= n;x += lowbit(x))
tre[x] += k;
return ;
}
int query(int x) {
int ans = 0;
for (;x > 0;x -= lowbit(x))
ans += tre[x];
return ans;
}
void change(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) swap (u, v);
modify (id[top[v]], 1);
modify (id[v] + 1, -1);
v = fa[top[v]];
}
if (dep[u] > dep[v]) swap (u, v);
modify (id[u] + 1, 1);
modify (id[v] + 1, -1);
return ;
}
int main() {
scanf ("%d%d", &n, &m);
for (int i = 1;i < n; ++ i) {
int u, v;
scanf ("%d%d", &u, &v);
add(u, v), add(v, u);
}
dfs1 (1, 1);
dfs2 (1, 1);
while (m --) {
char opt;
scanf (" %c", &opt);
if (opt == 'P') {
int u, v;
scanf ("%d%d", &u, &v);
change (u, v);
}
else if (opt == 'Q') {
int u, v;
scanf ("%d%d", &u, &v);
if (dep[u] > dep[v])
printf ("%d\n", query (id[u]));
else printf ("%d\n", query (id[v]));
}
}
return 0;
}