【 Gym - 101138J 】Valentina and the Gift Tree(树链剖分)

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100005
#define inf (1LL<<60)
#define ll long long
using namespace std;
struct edge{
	int to,next;
}e[N<<1];
int head[N],cnt;
int n,q,g[N];
int dep[N],fa[N],siz[N],son[N];
int top[N],rk[N],w,id[N];
void add(int u,int v){
	e[++cnt]=(edge){v,head[u]};head[u]=cnt;
}
void dfs1(int u){
	siz[u]=1;
	for(int i=head[u],v;i;i=e[i].next)if(!dep[v=e[i].to]){
		fa[v]=u;
		dep[v]=dep[u]+1;
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v])son[u]=v;
	}
}
void dfs2(int u,int f){
	top[u]=f;
	rk[u]=++w;
	id[w]=u;
	if(!son[u])return;
	dfs2(son[u],f);
	for(int i=head[u],v;i;i=e[i].next){
		v=e[i].to;
		if(v==son[u]||v==fa[u])continue;
		dfs2(v,v);
	}
}

#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
struct node{
	ll s,sum,suml,sumr;
	node(){
		sum=0,s=suml=sumr=-inf;
	}
}tr[N<<2];
void pushUp(node& x,node ls,node rs){
	x.s=max(max(ls.s,rs.s),ls.sumr+rs.suml);
	x.sum=ls.sum+rs.sum;
	x.suml=max(ls.suml,ls.sum+rs.suml);
	x.sumr=max(rs.sumr,rs.sum+ls.sumr);
}
void build(int l,int r,int x){
	if(l==r){
		tr[x].s=tr[x].suml=tr[x].sumr=tr[x].sum=g[id[l]];
		return;
	}
	int m=l+r>>1;
	build(lson);build(rson);
	pushUp(tr[x], tr[x<<1], tr[x<<1|1]);
}
node query(int L,int R,int l,int r,int x){
	if(L<=l&&r<=R)return tr[x];
	int m=l+r>>1;
	if(R<=m)return query(L,R,lson);
	if(L>m) return query(L,R,rson);
	node now;
	pushUp(now, query(L,R,lson), query(L,R,rson));
	return now;
}

int main() {
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++)
		scanf("%d%d",&u,&v), add(u,v), add(v,u);
	for(int i=1;i<=n;i++) scanf("%d",&g[i]);
	dep[1]=1, dfs1(1), dfs2(1,1), build(1,n,1);
	
	scanf("%d",&q);
	while(q--){
		int a,b;node la,ra;
		scanf("%d%d",&a,&b);
		int ta=top[a],tb=top[b];
		while(ta!=tb){
			if(dep[ta]<dep[tb])
				pushUp(ra, query(rk[tb],rk[b],1,n,1), ra), b=fa[tb], tb=top[b];
			else pushUp(la, query(rk[ta],rk[a],1,n,1), la), a=fa[ta], ta=top[a];
		}
		if(dep[a]<dep[b]) pushUp(ra, query(rk[a],rk[b],1,n,1), ra);
		else pushUp(la, query(rk[b],rk[a],1,n,1), la);
		printf("%lld\n",max(max(la.s,ra.s),la.suml+ra.suml));
	}
	return 0;
}