令f(x)表示每个点的权值，初始化都是0
操作：
- 令f(x) = w, 且所有点y的值 + w - dis(x, y)
- f(x) = min(f(x,) 0);
- 查询f(x);
设计到的操作有
- 区间修改
- 区间查询
对于第一个操作，修改某个点的值，然后把所有点都加上w，再减去与这个点的距离。明显无法直接维护，因为无法(O(1))找到dis(x,y)
可以O(logn)LCA找到dis(v,u) = dis(v) + dis(u) - 2dis(lca)
有O(1)何必O(logn)
比如对红色点操作，那么对于根需要 + w - 3，对于蓝色点需要 + w - 3 - 2，其中2就是蓝色点到根的深度。但对于根到w这一段区间的点，发现用这种方法，权值减少了2，那么我们对于这一个操作，还需要进行区间修改，把[1,x]这段区间加上2
转换为到根结点的距离即可，那么每次查找距离就是deep[x],也就是x点的深度。那么这样操作后[1,x]这条链上都要加上2
设ss表示w之和，cc表示1操作的次数
对于第三个操作，查询这个点的权值，按理说直接
ss - cc * depth[x] + QueryOnTree(1, x)即可
但是还有第二个操作，取最小值操作。假如我利用上面公式算出的值是正数，那么取最小值操作后，我(f(x))要减去这个值，那就利用val[x]进行维护下，表示我取最小值时，最小值不是本身，而是0时的一个损失量。
那么每个结点的权值查询就是
ans = ss - cc * depth[x] + QueryOnTree(1, x) + val[x];
对于全部点修改，而且修改值取决于到x点的距离时，可以采用把这个权值转换为根的修改，那么对于每次查询，只需要用deep深度即可
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
const int M = 1e5 + 5;
struct Edge{
int to, next;
}e[M << 1];
int head[N], tot;
void add(int u, int v){
e[++tot].to = v;
e[tot].next = head[u];
head[u] = tot;
}
int depth[N], fa[N], son[N], siz[N];
void dfs1(int now, int fath){
fa[now] = fath, depth[now] = depth[fath] + 1;
siz[now] = 1;
for(int i = head[now]; i; i = e[i].next) {
int v = e[i].to;
if(v != fath) {
dfs1(v, now);
siz[now] += siz[v];
if(siz[v] > siz[son[now]]) son[now] = v;
}
}
}
ll val[N];
int dfn[N], cnt, top[N];
void dfs2(int u, int rt){
dfn[u] = ++cnt;
top[u] = rt;
if(son[u]) dfs2(son[u], rt);
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if(v != fa[u] && v != son[u]) dfs2(v, v);
}
}
struct Tree{
int l, r;
ll lazy, sum;
#define l(p) tree[p].l
#define r(p) tree[p].r
#define sum(p) tree[p].sum
#define lson(p) p << 1
#define rson(p) p << 1 | 1
#define lazy(p) tree[p].lazy
}tree[N << 2];
void build(int p, int l, int r){
l(p) = l, r(p) = r;
sum(p) = lazy(p) = 0;
if(l == r) return;
int mid = (l + r) >> 1;
build(lson(p), l, mid); build(rson(p), mid + 1, r);
}
void pushup(int p){
sum(p) = sum(lson(p)) + sum(rson(p));
}
void push(int p, int lazy){
lazy(p) += lazy;
sum(p) += (r(p) - l(p) + 1) * lazy;
}
void pushdown(int p){
if(lazy(p)) {
push(lson(p), lazy(p));
push(rson(p), lazy(p));
lazy(p) = 0;
}
}
void update(int p, int l, int r, int val){
if(l <= l(p) && r(p) <= r) {
push(p, val);
return;
}
pushdown(p);
int mid = (l(p) + r(p)) >> 1;
if(l <= mid) update(lson(p), l, r, val);
if(r > mid) update(rson(p), l, r, val);
pushup(p);
}
ll query(int p, int l, int r){
if(l <= l(p) && r(p) <= r) {
return sum(p);
}
pushdown(p);
ll ans = 0;
int mid = (l(p) + r(p)) >> 1;
if(l <= mid) ans += query(lson(p), l, r);
if(r > mid) ans += query(rson(p), l, r);
return ans;
}
void ModifyOnTree(int u, int v, int val){
while(top[u] != top[v]) {
if(depth[top[u]] < depth[top[v]]) swap(u, v);
update(1, dfn[top[u]], dfn[u], val);
u = fa[top[u]];
}
if(depth[u] > depth[v]) swap(u, v);
update(1, dfn[u], dfn[v], val);
}
ll QueryOnTree(int u, int v){
ll ans = 0;
while(top[u] != top[v]){
if(depth[top[u]] < depth[top[v]]) swap(u, v);
ans += query(1, dfn[top[u]], dfn[u]);
u = fa[top[u]];
}
if(depth[u] > depth[v]) swap(u, v);
ans += query(1, dfn[u], dfn[v]);
return ans;
}
void init(int n){
cnt = 0; tot = 0;
for(int i = 1; i <= n; i++)
head[i] = son[i] = val[i] = 0;
}
// 上面都是树剖模板 + 初始化
void solve(){
int n, m;
scanf("%d%d", &n, &m);
init(n);
for(int i = 1, u, v; i < n; i++) {
scanf("%d%d", &u, &v);
add(u, v); add(v, u);
}
dfs1(1, 0); dfs2(1, 1);
build(1, 1, n);
int op, x, w;
ll ss = 0, ans = 0, cc = 0;
for (int i = 1; i <= m; i++) {
scanf("%d", &op);
if (op == 1) {
scanf("%d%d", &x, &w);
ss += w - depth[x], cc++;
ModifyOnTree(1, x, 2);
} else if (op == 2) {
scanf("%d", &x);
ans = ss - cc * depth[x] + QueryOnTree(1, x) + val[x];
if (ans > 0) val[x] -= ans;
} else {
scanf("%d", &x);
ans = ss - cc * depth[x] + QueryOnTree(1, x) + val[x];
printf("%lld
", ans);
}
}
}
int main(){
int t;
scanf("%d", &t);
while(t--) solve();
return 0;
}