#include <bits/stdc++.h>
using namespace std;

inline int read(){
	int sum=0,f=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()){
		f |= (ch=='-');
	}
	for(;isdigit(ch);ch=getchar()){
		sum = ((sum<<1)+(sum<<3)+(ch^48));
	}
	return f?-sum:sum;
}

#define int long long
#define mid ((l+r)>>1)
#define Lson (rt<<1),l,mid
#define Rson ((rt<<1)|1),mid+1,r
#define len (r-l+1)

const int maxn = 400010;

int n,m,tot,cnt,now;
int a[maxn],sum[maxn],lazy[maxn],edge[maxn],nxt[maxn],head[maxn];
int deep[maxn],fa[maxn],size[maxn],wson[maxn],dfn[maxn],top[maxn],pre[maxn];

struct tree{
	void build(int rt,int l,int r){
		if(l == r){
			sum[rt] = a[pre[l]];
			return ;
		}
		build(Lson);
		build(Rson);
		sum[rt] += sum[rt<<1]+sum[rt<<1|1];
	}
	void pushdown(int rt,int lenn){
		lazy[rt<<1] += lazy[rt];
		lazy[rt<<1|1] += lazy[rt];
		sum[rt<<1] += lazy[rt]*(lenn-(lenn>>1));
		sum[rt<<1|1] += lazy[rt]*(lenn>>1);
		lazy[rt] = 0;
	}
	void query(int rt,int l,int r,int L,int R){
		if(L<=l && r<=R){
			now += sum[rt];
			return ;
		}
		if(lazy[rt]){
			pushdown(rt,len);
		}
		if(L <= mid){
			query(Lson,L,R);
		}
		if(R > mid){
			query(Rson,L,R);
		}
	}
	void update(int rt,int l,int r,int L,int R,int v){
		if(L<=l && r<=R){
			lazy[rt] += v;
			sum[rt] += v*len;
			return ;
		}
		if(lazy[rt]){
			pushdown(rt,len);
		}
		if(L <= mid){
			update(Lson,L,R,v);
		}
		if(R > mid){
			update(Rson,L,R,v);
		}
		sum[rt] = sum[rt<<1]+sum[rt<<1|1];
	}
}t1;

struct Tree{
	void add(int u,int v){
		edge[++tot] = v;
		nxt[tot] = head[u];
		head[u] = tot;
	}
	void dfs1(int x,int father){
		size[x] = 1;
		for(int i=head[x];i;i=nxt[i]){
			int y = edge[i];
			if(y == father){
				continue;
			}
			deep[y] = deep[x]+1;
			fa[y] = x;
			dfs1(y,x);
			size[x] += size[y];
			if(size[y] > size[wson[x]]){
				wson[x] = y;
			}
		}
	}
	void dfs2(int x,int tp){
		dfn[x] = ++cnt;
		pre[cnt] = x;
		top[x] = tp;
		if(wson[x]){
			dfs2(wson[x],tp);
		}
		for(int i=head[x];i;i=nxt[i]){
			int y = edge[i];
			if((y==wson[x]) || (y==fa[x])){
				continue;
			}
			dfs2(y,y);
		}
	}
	void Update(int a,int b,int v){
		while(top[a] != top[b]){
			if(deep[top[a]] < deep[top[b]]){
				swap(a,b);
			}
			t1.update(1,1,n,dfn[top[a]],dfn[a],v);
			a = fa[top[a]];
		}
		if(deep[a] < deep[b]){
			swap(a,b);
		}
		t1.update(1,1,n,dfn[a],dfn[b],v);
	}
	int Query(int a,int b){
		int ans = 0;
		while(top[a] != top[b]){
			if(deep[top[a]] < deep[top[b]]){
				swap(a,b);
			}
			now = 0;
			t1.query(1,1,n,dfn[top[a]],dfn[a]);
			ans += now;
			a = fa[top[a]];
		}
		if(deep[a] < deep[b]){
			swap(a,b);
		}
		now = 0;
		t1.query(1,1,n,dfn[a],dfn[b]);
		ans += now;
		return ans;
	}
	void Updates(int x,int v){
		t1.update(1,1,n,dfn[x],dfn[x]+size[x]-1,v);
	}
	int Querys(int x){
		return t1.query(1,1,n,dfn[x],dfn[x]+size[x]-1);
	}
}t2;

signed main(){
	t2.dfs1(1,0);
	t2.dfs2(1,1);
	t1.build(1,1,n);
	return 0;
}
/*
树链剖分

注： 链上 修改/查询 最后一步调用有疑
*/

链上查询函数 Query 最后一步应是

t1.query(1,1,n,dfn[a],dfn[b]);

还是

t1.query(1,1,n,dfn[top[a]],dfn[a]);

?

链上修改函数 Update 中同问。

感谢！