算是一个小技巧吧，所有题目在给定或者求出计算公式之后，都可以去朝着把恒定的值或者成对出现的值单独拿出来维护
比如这个题 w - dis(x,y) = w - dep[x] - dep[y] + w * dep[LCA(x, y)] ，我们就会发现 w - dep[x] 为定值 , dep[y]可以通过维护次数
那么重点在于dep[LCA(x,y)]，这个地方是一个小技巧，我们可以通过修改根到x的路径上的每一条边，使得每条边权值+1，然后在
维护答案的时候，query一下根到x的路径上的和就好了。具体实现的时候可以边塞点，也可以直接通过点权维护，只不过要保
证Update链后的dep[LCA(x,y)] 能和 dep[x], dep[y] 对应上。参看具体代码
//#define LOCAL #include <bits/stdc++.h> using namespace std; #define ll long long #define mem(a, b) memset(a,b,sizeof(a)) #define sz(a) (int)a.size() #define INF 0x3f3f3f3f #define DNF 0x7f #define DBG printf("this is a input\n") #define fi first #define se second #define mk(a, b) make_pair(a,b) #define pb push_back #define LF putchar('\n') #define SP putchar(' ') #define p_queue priority_queue #define CLOSE ios::sync_with_stdio(0); cin.tie(0) template<typename T> void read(T &x) {x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;} template<typename T, typename... Args> void read(T &first, Args& ... args) {read(first);read(args...);} template<typename T> void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');} template<typename T, typename ... Ts> void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}} using namespace std; ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } const int N = 6e4 + 5; int T, n , m; int head[N] , cnt; struct node1{ int next , t; }edge[N << 1]; void add (int f, int t) { edge[cnt].t = t; edge[cnt].next = head[f]; head[f] = cnt ++; } int dfn[N] , siz[N] , dep[N], son[N], top[N], id[N], times; int fa[N]; ll S, delta[N], tot; void dfs1(int u) { siz[u] = 1; for (int i = head[u] ; i != -1 ; i = edge[i].next) { int v = edge[i].t; if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; dfs1(v); siz[u] += siz[v]; if(siz[v] > siz[son[u]]) son[u] = v; } } } void dfs2(int u , int t) { top[u] = t; dfn[u] = ++ times; id[times] = u; if (son[u]) dfs2(son[u], t); for (int i = head[u] ; i != -1 ; i = edge[i].next) { int v = edge[i].t; if (v != son[u] && v != fa[u]) dfs2(v, v); } } struct tree_node { int l , r; ll sum , lz; }tree[N << 2]; void pushdown(int i) { if(tree[i].lz != 0) { tree[i*2].lz += tree[i].lz; tree[i*2+1].lz += tree[i].lz; int mid = (tree[i].l+tree[i].r)/2; tree[i*2].sum += tree[i].lz*(mid - tree[i*2].l + 1); tree[i*2+1].sum += tree[i].lz*(tree[i*2+1].r - mid); tree[i].lz = 0; } return ; } void build(int i , int l , int r) { tree[i].l = l, tree[i].r = r, tree[i].lz = 0, tree[i].sum = 0; if(l == r) { tree[i].sum = 0; return ; } int mid = (l + r) >> 1; build(i*2,l,mid); build(i*2+1,mid+1,r); tree[i].sum = tree[i*2].sum + tree[i*2+1].sum; } void update(int i , int l , int r , int k) { if(tree[i].l >= l && tree[i].r <= r) { tree[i].sum += (tree[i].r-tree[i].l+1)*k; tree[i].lz += k; return ; } pushdown(i); if(l <= tree[i*2].r) update(i*2,l,r,k); if(tree[i*2+1].l <= r) update(i*2+1,l,r,k); tree[i].sum = tree[i*2].sum + tree[i*2+1].sum; return ; } ll search(int i , int l , int r) { if(tree[i].l >= l && tree[i].r <= r) { return tree[i].sum; } if(l > tree[i].r || r < tree[i].l) return 0; pushdown(i); ll ans = 0; if(tree[i*2].r >= l) { ans += search(i * 2, l, r); } if(tree[i*2+1].l <= r) { ans += search(i * 2 + 1, l, r); } return ans; } void TreeAdd(int x, int y, int val) { while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x,y); update(1,dfn[top[x]], dfn[x], val); x = fa[top[x]]; } if(dep[x] > dep[y]) swap(x,y); update(1,dfn[x],dfn[y],val); } ll TreeSum(int x, int y) { ll ans = 0; while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x,y); ans = ans + search(1,dfn[top[x]], dfn[x]); x = fa[top[x]]; } if(dep[x] > dep[y]) swap(x,y); ans += search(1,dfn[x],dfn[y]); return ans; } ll Get (int x) { return S - 1ll * tot * dep[x] + 2ll * TreeSum(1, x); } void Init() { S = times = cnt = tot = 0; mem(head,-1); mem(fa,0); mem(dfn,0); mem(siz,0); mem(dep,0); mem(son,0); mem(top,0); mem(id,0); mem(delta,0); } int main() { read(T); while (T--) { Init(); read (n , m); for (int i = 1 ; i < n ; i ++) { int u , v; read (u , v); add (u, v); add (v ,u); } build (1 , 1, n); dep[1] = 1; dfs1(1); dfs2(1, 1); for (int i = 1 ; i <= m ; i ++) { int op , x , w; read (op , x); if (op == 1) { read (w); S += w - dep[x]; tot ++; TreeAdd (1, x, 1); } else if (op == 2) { ll ans = Get(x) - delta[x]; if (ans > 0) delta[x] += ans; } else write(Get(x) - delta[x]), LF; } } } /* 4 1 2 2 3 0 1 3 1 1 2 3 2 */当然 dep[1]也可以从0开始，只不过如果从0开始的话，需要在update(1,x,1)后，再update(1,1,-1) ，否则dep不能保持一致
用这组数据理解一下就好了
1 5 6 1 2 1 3 2 4 2 5 1 5 5 3 2模拟一下整个过程就明白了
