传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5957
题意:D(u,v)是节点u和节点v之间的距离，S(u,v)是一系列满足D(u,x)<=k的点的集合，操作1：将S(u,k)内节点权值增加或者减小，操作2：查询S(u,k)内节点的权值和
题解:因为题目说了查询和更新的距离小于等于k，k最大为2，所以很显然要分情况讨论k为0、1、2的情况
因为是多次更新，我们显然是需要用线段树来维护节点权值的
运用线段树和bfs序的知识我们知道
对一个棵树求BFS序后，深度相同的节点的序号是相邻的。
对于节点u，如果知道它儿子的最小BFS序号L和最大BFS序号R，那么它儿子的所有序号就在[L,R]中。
这样就比较方便对区间进行查询或者修改操作
根据题意可以知道：每次更新的时候
如果k==0，那么就只更新自己
如果k==1，那么就更新自己还有和自己相连的边，由于存在环的情况，所以我们要首先处理每个节点的入度，处理完入度的话，如果这个点的入度是1，那么证明这个点就不在环上，就更新他自己，他的儿子，他的父亲节点即可，如果这个点的入度大于1，那么这个点就在环上，稍微画个图就知道，环上就有左爸爸和右爸爸，将这两个节点给更新就好
如果k==2，那么情况就比较复杂了，首先是要更新自己，然后，和自己相连的边，和之前一样要判断环的情况，没有环的话，再讨论自己的爸爸节点还有儿子节点的情况，可能存在爸爸节点在环上、爸爸节点不在环上，儿子节点在环上、儿子节点不在环上，这样分类讨论完后即可
求和和更新差不多就不多讲了
代码有注释.
代码如下：
#include <map> #include <set> #include <cmath> #include <ctime> #include <stack> #include <queue> #include <cstdio> #include <cctype> #include <bitset> #include <string> #include <vector> #include <cstring> #include <iostream> #include <algorithm> #include <functional> #define PI acos(-1) #define eps 1e-8 #define fuck(x) cout<<#x<<" = "<<x<<endl; #define FIN freopen("input.txt","r",stdin); #define FOUT freopen("output.txt","w+",stdout); #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 //#pragma comment(linker, "/STACK:102400000,102400000") using namespace std; typedef long long LL; typedef pair<int, int> PII; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;} LL lcm(LL a, LL b) {return a / gcd(a, b) * b;} LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;} double dpow(double a, LL b) {double ans = 1.0; while (b) {if (b % 2)ans = ans * a; a = a * a; b /= 2;} return ans;} int n, q; struct node { int v, nxt, w; } edge[maxn]; int head[maxn]; int tot; void add_edge(int u, int v) { edge[tot].v = v; edge[tot].nxt = head[u]; head[u] = tot++; } int in[maxn]; void top() { queue<int>q; for (int i = 1; i <= n; i++) if (in[i] == 1) q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; ~i; i = edge[i].nxt) { int v = edge[i].v; if (in[v] > 1) { in[v]--; if (in[v] == 1) q.push(v); } } } } LL sum[maxn << 2], add[maxn << 2]; void build(int l, int r, int rt) { sum[rt] = add[rt] = 0; if (l == r) return; int m = (l + r) >> 1; build(lson); build(rson); } void PushDown(int m, int rt) { if (add[rt]) { add[rt << 1] += add[rt]; add[rt << 1 | 1] += add[rt]; sum[rt << 1] += add[rt] * (m - (m >> 1)); sum[rt << 1 | 1] += add[rt] * (m >> 1); add[rt] = 0; } } void PushUP(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void update(int L, int R, int c, int l, int r, int rt) { if (L == 0 || R == 0) return; if (L <= l && R >= r) { sum[rt] += (LL)(r - l + 1) * c; add[rt] += c; return; } PushDown(r - l + 1, rt); int m = (l + r) >> 1; if (L <= m) update(L, R, c, lson); if (R > m) update(L, R, c, rson); PushUP(rt); } LL query(int L, int R, int l, int r, int rt) { if (L == 0 || R == 0) return 0; if (L <= l && R >= r) return sum[rt]; PushDown(r - l + 1, rt); int m = (l + r) >> 1; LL ret = 0; if (L <= m) ret += query(L, R, lson); if (R > m) ret += query(L, R, rson); PushUP(rt); return ret; } int ver[maxn][2]; int p[maxn], fp[maxn], fa[maxn], sz; int sonL[maxn], sonR[maxn], ssonL[maxn], ssonR[maxn]; //设val[u]为节点u的权值，fa[u]为父亲,son[u]为儿子,sson[u]孙子 void bfs(int top) { //bfs序找最左和最右的区间 queue<int>q; q.push(top); while (!q.empty()) { int u = q.front(); q.pop(); sonL[u] = ssonL[u] = INF; sonR[u] = ssonR[u] = 0; for (int i = head[u]; i!=-1; i = edge[i].nxt) { int v = edge[i].v; if (in[v] > 1 || v == fa[u]) continue; //如果连的点在环上就不管 p[v] = ++sz; //继续打编号 fp[sz] = v; fa[v] = u; sonL[u] = min(sonL[u], p[v]); sonR[u] = max(sonR[u], p[v]); q.push(v); } ssonL[fa[u]] = min(ssonL[fa[u]], sonL[u]); ssonR[fa[u]] = max(ssonR[fa[u]], sonR[u]); } } void change(int u, int k, int d) { int father = fa[u]; //分类讨论 //如果k==0，那么就更新单个节点 //如果k==1，那么就更新u的儿子和爸爸还有自己 //1)需要讨论是否在环上，环上的话相当于有两个爸爸 //如果k==2，那么就更新u的儿子和孙子，u的爸爸和u的爷爷，还有自己 //1）需要讨论u是否在环上，环上的话，有两个爸爸和两个爷爷都要更新 //2）需要讨论u的儿子和孙子是否在环上 if (k == 0) update(p[u], p[u], d, 1, n, 1); else if (k == 1) { update(sonL[u], sonR[u], d, 1, n, 1); update(p[u], p[u], d, 1, n, 1); if (in[u] == 1) update(p[fa[u]], p[fa[u]], d, 1, n, 1); else { update(p[ver[u][0]], p[ver[u][0]], d, 1, n, 1); update(p[ver[u][1]], p[ver[u][1]], d, 1, n, 1); } } else if (k == 2) { //update(p[u],p[u],d,1,n,1); update(sonL[u], sonR[u], d, 1, n, 1); update(ssonL[u], ssonR[u], d, 1, n, 1); if (in[u] == 1) { update(p[fa[u]], p[fa[u]], d, 1, n, 1); update(sonL[fa[u]], sonR[fa[u]], d, 1, n, 1); if (in[fa[u]] == 1) { update(p[fa[fa[u]]], p[fa[fa[u]]], d, 1, n, 1); } else { update(p[ver[fa[u]][0]], p[ver[fa[u]][0]], d, 1, n, 1); update(p[ver[fa[u]][1]], p[ver[fa[u]][1]], d, 1, n, 1); } } else { update(p[u], p[u], d, 1, n, 1); int vv[2]; int cnt = 0; for (int i = 0; i < 2; i++) { int v = ver[u][i]; update(p[v], p[v], d, 1, n, 1); update(sonL[v], sonR[v], d, 1, n, 1); for (int j = 0; j < 2; j++) { if (ver[v][j] == u || ver[v][j] == ver[u][0] || ver[v][j] == ver[u][1]) continue; if (cnt > 0 && ver[v][j] == vv[cnt - 1]) continue; vv[cnt++] = ver[v][j]; } } for (int i = 0; i < cnt; i++) { update(p[vv[i]], p[vv[i]], d, 1, n, 1); } } } } int get_ans(int u, int k) { //分类讨论 //如果k==0，那么就查询单个节点 //如果k==1，那么就查询u的儿子和爸爸还有自己 //1)需要讨论是否在环上，环上的话相当于有两个爸爸 //如果k==2，那么就查询u的儿子和孙子，u的爸爸和u的爷爷，还有自己 //1）需要讨论u是否在环上，环上的话，有两个爸爸和两个爷爷都要查询 //2）需要讨论u的儿子和孙子是否在环上 int ans = 0; if (k == 0) ans += query(p[u], p[u], 1, n, 1); else if (k == 1) { ans += query(sonL[u], sonR[u], 1, n, 1); ans += query(p[u], p[u], 1, n, 1); if (in[u] == 1) ans += query(p[fa[u]], p[fa[u]], 1, n, 1); else { ans += query(p[ver[u][0]], p[ver[u][0]], 1, n, 1); ans += query(p[ver[u][1]], p[ver[u][1]], 1, n, 1); } } else if (k == 2) { //update(p[u],p[u],d,1,n,1); ans += query(sonL[u], sonR[u], 1, n, 1); ans += query(ssonL[u], ssonR[u], 1, n, 1); if (in[u] == 1) { ans += query(p[fa[u]], p[fa[u]], 1, n, 1); ans += query(sonL[fa[u]], sonR[fa[u]], 1, n, 1); if (in[fa[u]] == 1) { ans += query(p[fa[fa[u]]], p[fa[fa[u]]], 1, n, 1); } else { ans += query(p[ver[fa[u]][0]], p[ver[fa[u]][0]], 1, n, 1); ans += query(p[ver[fa[u]][1]], p[ver[fa[u]][1]], 1, n, 1); } } else { ans += query(p[u], p[u], 1, n, 1); int vv[2]; int cnt = 0; for (int i = 0; i < 2; i++) { int v = ver[u][i]; ans += query(p[v], p[v], 1, n, 1); ans += query(sonL[v], sonR[v], 1, n, 1); for (int j = 0; j < 2; j++) { if (ver[v][j] == u || ver[v][j] == ver[u][0] || ver[v][j] == ver[u][1]) continue; if (cnt > 0 && ver[v][j] == vv[cnt - 1]) continue; vv[cnt++] = ver[v][j]; } } for (int i = 0; i < cnt; i++) { ans += query(p[vv[i]], p[vv[i]], 1, n, 1); } } } return ans; } int main() { #ifndef ONLINE_JUDGE FIN #endif int T; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { in[i] = 0; fa[i] = 0; head[i] = -1; } tot = 0; sz=0; int u, v; for (int i = 1; i <= n; i++) { scanf("%d%d", &u, &v); in[v]++; in[u]++; add_edge(u, v); add_edge(v, u); } top(); for (int u = 1; u <= n; u++) {//遍历每一个节点 if (in[u] > 1) {//如果节点的入度大于1 int j = 0; for (int i = head[u]; i!=-1; i = edge[i].nxt) { //这个节点所有的子树 int v = edge[i].v; if (in[v] > 1) {//如果这个点在环上 ver[u][j++] = v;//记录点u在环上连的是哪两个点 } } p[u] = ++sz;//给点u编号 fp[sz] = u; bfs(u); } } build(1, n, 1); char op[10]; int k, d; scanf("%d", &q); while (q--) { scanf("%s", op); if (op[0] == 'M') { scanf("%d%d%d", &u, &k, &d); change(u, k, d); } else { scanf("%d%d", &u, &k); printf("%d ", get_ans(u, k)); } } } }