树上前缀和

树上前缀和
问题描述
有一棵n个点的树，每个点i有点树v[i]，q个询问求点u到点v最简路径上所有点权之和
输入格式
第一行n,q表示有n个点,q个询问
第二行n个整数表示每个点的权
下面n-1每行两个整数x,y描述边的信息
下面q行每行两个整数u,v表示询问的两个点
输出
q行，每行为u到v最简路径上的点权和
样例
in
5 5
1 2 3 4 5

1 2
2 3
1 4
1 5
1 5
2 3
1 4
2 5
3 5
out
6
5
5
8
11

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
struct node{
	int to;
	int nxt;
}E[maxn<<1];
int v[maxn],h[maxn],f[maxn][25],dep[maxn],sum[maxn],lg[maxn],etot;
void addedge(int x,int y)
{
	E[++etot].to=y;
	E[etot].nxt=h[x];
	h[x]=etot;
}
void dfs(int u,int fa)
{
	f[u][0]=fa;
	dep[u]=dep[fa]+1;
	sum[u]+=sum[fa]+v[u];
	for (int i=1;i<=lg[dep[u]];i++)
	{
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for (int i=h[u];i;i=E[i].nxt)
	{
		int v=E[i].to;
		if (v!=fa)
		{
			dfs(v,u);
		}	
	}	
}
int lca(int x,int y)
{
	if (dep[x]<dep[y]) swap(x,y);
	int d=dep[x]-dep[y];
	while(d)
	{
		int k=lg[d];
		x=f[x][k];
		d=d-(1<<k);
	}
	if (x==y) return x;
	for (int i=lg[dep[x]];i>=0;i--)
	{
		if (f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
int main()
{
	int n,q;
	cin>>n>>q; 
	for (int i=1;i<=n;i++) cin>>v[i];
	for (int i=2;i<=n;i++) lg[i]=lg[i<<1]+1;
	for (int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		addedge(x,y);
		addedge(y,x);
	}
	dfs(1,0);
	for (int i=1;i<=q;i++)
	{
		int u,v;
		cin>>u>>v;
		int k=lca(u,v);
		cout<<sum[u]+sum[v]-sum[k]-sum[f[k][0]]<<endl;
	}
}