题6 - 小沙的身法

寒假训练营2的一道题

给定一棵树的路径关系，每个结点有一个高度，从低到高需要花费它俩高度之差的体力。有m个询问，每次询问从 x 到 y 结点需要花费多少体力（刚开始在地面，需要从地面上到结点x）。

思路：因为没有修改操作，直接前缀和即可（ max(0,差值) 的前缀和）。做dfs序的前缀和与后缀和。由x到LCA(x,y)的过程中，是从dfn大的一端跑向小的一端，因此用后缀和；由y到LCA(x,y)的过程中，是从dfn小的一端跑向大的一端，因此用前缀和。

代码：

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=5,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a ????; b MOD-2
ll lowbit(ll x){return x&(-x);}

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,minn,maxx,ans;
ll a[N],b[N],c[N],head[N],dx[5]={0,0,-1,1},dy[5]={-1,1,0,0};
double dans;
bool vis,flag;
char mapp,zz;
struct qq{ll x,y,z;}q;
struct tree{ll l,r,tag,sum;}trs[N];
struct Tree{ll fa,dep,dfn,siz,son,top,w;}tr[N];
struct Trp{ll l,r,fat,dep,n,w;}trp;
struct E{ll to,nxt,w;}eg[N*2];
struct matrix{ll n,m[M][M];};
struct complx{
	double r,i;
	complx(){}
	complx(double r,double i):r(r),i(i){}
	complx operator+(const complx& rhs)const{return complx (r+rhs.r,i+rhs.i);}
	complx operator-(const complx& rhs)const{return complx (r-rhs.r,i-rhs.i);}
	complx operator*(const complx& rhs)const{return complx (r*rhs.r-i*rhs.i,i*rhs.r+r*rhs.i);}
	void operator+=(const complx& rhs){r+=rhs.r,i+=rhs.i;}
	void operator*=(const complx& rhs){r=r*rhs.r-i*rhs.i,i=r*rhs.i+i*rhs.r;}
	void operator/=(const double& x){r/=x,i/=x;}
	complx conj(){return complx(r,-i);}
}; 

bool cmp(qq u,qq v){
    return u.x*v.y>v.x*u.y;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun??

pair<ll,ll>pre;
vector<ll>v;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
deque<qq>sq;
map<ll,ll>mp;
bitset<M>bi;

void add(ll u,ll v,ll w){
	eg[++cnt].to=v;
	eg[cnt].nxt=head[u];
	eg[cnt].w=w;
	head[u]=cnt;
}

void dfs1(ll x,ll ac){
	tr[x].fa=ac;
	tr[x].dep=tr[tr[x].fa].dep+1;
	tr[x].siz=1;
	ll k=head[x];
	while(k){
		ll y=eg[k].to;
		if(y!=ac){
			dfs1(y,x);
			tr[x].siz+=tr[y].siz;
			if(!tr[x].son||tr[y].siz>tr[tr[x].son].siz)tr[x].son=y;
		}
		k=eg[k].nxt;
	}
}

void dfs2(ll x,ll pos){
	tr[x].dfn=++tot;
	tr[x].top=pos;
	a[tot]=tr[x].w;
	if(!tr[x].son)return;
	dfs2(tr[x].son,pos);
	ll k=head[x];
	while(k){
		ll y=eg[k].to;
		if(y!=tr[x].fa&&y!=tr[x].son)dfs2(y,y);
		k=eg[k].nxt;
	} 
}

ll qchain(ll x,ll y){
	ll res=0,hx=0,hy=0;
	while(tr[x].top!=tr[y].top){
		if(tr[tr[x].top].dep<tr[tr[y].top].dep){
			res+=max(0ll,hy-tr[y].w);
			res+=b[tr[y].dfn]-b[tr[tr[y].top].dfn];
			hy=tr[tr[y].top].w;
			y=tr[tr[y].top].fa;
		}
		else{
			res+=max(0ll,tr[x].w-hx);
			res+=c[tr[tr[x].top].dfn]-c[tr[x].dfn];
			hx=tr[tr[x].top].w;
			x=tr[tr[x].top].fa;
		}
	}
	if(tr[x].dep>tr[y].dep){
		res+=max(0ll,hy-tr[y].w);
		res+=max(0ll,tr[x].w-hx);
		res+=c[tr[y].dfn]-c[tr[x].dfn];
	}
	else{
		res+=max(0ll,hy-tr[y].w);
		res+=max(0ll,tr[x].w-hx);
		res+=b[tr[y].dfn]-b[tr[x].dfn];
	}
	return res;
}

int main(){
	scanf("%lld%lld",&n,&m);
	L(i,1,n)scanf("%lld",&tr[i].w);
	cnt=0;
	L(i,1,n-1){
		scanf("%lld%lld",&x,&y);
		add(x,y,0);
		add(y,x,0);
	}
	tot=0;
	dfs1(1,0);
	dfs2(1,1);
	a[0]=0,a[n+1]=0,b[0]=0,c[n+1]=0;
	L(i,1,n)b[i]=b[i-1]+max(0ll,a[i]-a[i-1]);
	R(i,n,1)c[i]=c[i+1]+max(0ll,a[i]-a[i+1]);
	//L(i,1,n)printf("%lld ",tr[i].dfn);printf("\n");
	
	L(i,1,m){
		scanf("%lld%lld",&x,&y);
		printf("%lld\n",qchain(x,y));
	}
}