好像很少有关于top数组性质的博客。

for(int i=top[x];fa[i];i=top[fa[i]])

可以遍历所有子树中含有x节点的重链链头节点（或叶子节点），由于重链不超过log(n)个,所以这个循环复杂度是O(logN)的。
设i是重链链头节点，f是i的父节点，则i是f的轻儿子。
所以，如果有操作：对于x节点，他的所有儿子均加上不同的值，且这个值只与儿子节点自身和提供的值有关，那么，可以只更新x节点的重儿子，在x节点加上标记，查询的时候加上答案即可。

D. Tree Queries

Hanh is a famous biologist. He loves growing trees and doing experiments on his own garden.

One day, he got a tree consisting of n vertices. Vertices are numbered from 1 to n. A tree with n vertices is an undirected connected graph with n−1 edges. Initially, Hanh sets the value of every vertex to 0.

Now, Hanh performs q operations, each is either of the following types:

Type 1. Hanh selects a vertex v and an integer d. Then he chooses some vertex r uniformly at random, lists all vertices u such that the path from r to u passes through v. Hanh then increases the value of all such vertices u by d.
Type 2. Hanh selects a vertex v and calculates the expected value of v.
Since Hanh is good at biology but not math, he needs your help on these operations.

Input
The first line contains two integers n and q (1≤n,q≤150000) — the number of vertices on Hanh’s tree and the number of operations he performs.

Each of the next n−1 lines contains two integers u and v (1≤u,v≤n), denoting that there is an edge connecting two vertices u and v. It is guaranteed that these n−1 edges form a tree.

Each of the last q lines describes an operation in either formats:

1vd(1≤v≤n,0≤d≤107)1 v d (1≤v≤n,0≤d≤10^7)1vd(1≤v≤n,0≤d≤107), representing a first-type operation.
2v(1≤v≤n)2 v (1≤v≤n)2v(1≤v≤n), representing a second-type operation.
It is guaranteed that there is at least one query of the second type.

Output
For each operation of the second type, write the expected value on a single line.

Let M=998244353, it can be shown that the expected value can be expressed as an irreducible fraction pq, where p and q are integers and q≢0(modM). Output the integer equal to p⋅q−1modM. In other words, output such an integer x that 0≤x<M and x⋅q≡p(modM).

Example
input

5 12
1 2
1 3
2 4
2 5
1 1 1
2 1
2 2
2 3
2 4
2 5
1 2 2
2 1
2 2
2 3
2 4
2 5

output

1
199648871
399297742
199648871
199648871
598946614
199648873
2
2
2

分析r相对于v的位置容易得如何更新答案，对给定节点v，需要对整棵树操作一次和子树v操作一次以及对v的每个子节点u，减去dsiz[son[u]]inv，这样做是O(N)的复杂度，只能过11个点，当然，也可以按子树大小分块，复杂度降到了 O(N)O(\sqrt N)O(N )，但是好像码量有些大。
所以，可以只更新v节点的重儿子，轻儿子的更新标记放置在v节点上，因为轻儿子一定是重链头结点或叶子节点，所以查询的时候减去多余的答案即可。

#include using namespace std; char buf[120],*_=buf,*__=buf; #define gc() (_==__&&(__=(_=buf)+fread(buf,1,1 #define TT templateinline TT bool read(T &x){ x=0;char c=gc();bool f=0; while(c48||c>57){if(c==EOF)return 0;f^=(c=='-'),c=gc();} while(47c&&c58)x=(x3)+(x1)+(c^48),c=gc(); if(f)x=-x;return 1; } TT bool read(T&a,T&b){return read(a)&&read(b);} TT bool read(T&a,T&b,T&c){return read(a)&&read(b)&&read(c);} typedef long long ll; const ll MAXN=1e5+8,mod=1e9+8,inf=0x3f3f3f3f; #define lowbit(x) (x&(-x)) #define Max(a,b) if(b>a)a=b #define Min(a,b) if(b int n; struct E{int y,nt;}e[MAXN1]; int head[MAXN],cnt; inline void add(int x,int y){ e[++cnt].y=y; e[cnt].nt=head[x]; head[x]=cnt; } int dep[MAXN],siz[MAXN],fa[MAXN],son[MAXN]; void dfs1(int x){ siz[x]=1,dep[x]=dep[fa[x]]+1; for(int i=head[x];i;i=e[i].nt){ int y=e[i].y; if(siz[y])continue; fa[y]=x; dfs1(y); siz[x]+=siz[y]; if(!son[x]||siz[son[x]]siz[y])son[x]=y; } } int id[MAXN],top[MAXN],idcnt; ll d[MAXN]; void dfs2(int x,int tp){ id[x]=++idcnt; top[x]=tp; if(son[x])dfs2(son[x],tp); for(int i=head[x];i;i=e[i].nt){ int y=e[i].y; if(id[y])continue; dfs2(y,y); } } inline void presum_add(int p,ll v){ while(pn){ (d[p]+=v)%=mod; p+=lowbit(p); } } inline ll ask(int p){ ll res=0; while(p){ (res+=d[p])%=mod; p-=lowbit(p); }return res; } inline void subtree_add(const int x,const ll v){ presum_add(id[x],v); presum_add(id[x]+siz[x],mod-v); } ll qpow(ll x,ll k){ ll res=1; while(k){ if(k&1)res=res*x%mod; x=x*x%mod;k>>=1; }return res; } ll lazy[MAXN]; int main() { int q; read(n,q); for(int i=1,x,y;in;++i){ read(x,y); add(x,y); add(y,x); } dfs1(1); dfs2(1,1); int op,x; ll inv=qpow(n,mod-2),val; while(q--){ read(op,x); if(op==1){ read(val); (lazy[x]+=val)%=mod; subtree_add(x,(n-siz[x])*val%mod); subtree_add(1,siz[x]*val%mod); if(!son[x])continue; subtree_add(son[x],mod-siz[son[x]]*val%mod); } else{ ll res=ask(id[x]); for(int i=top[x];fa[i];i=top[fa[i]]){ (res+=mod-siz[i]*lazy[fa[i]]%mod)%=mod; } printf("%I64d\n",res*inv%mod); } } return 0; }