浅谈 - 树链剖分

前言：其实只是最近练了一些题后，总结一下下

• 树链剖分，其实就是把一棵树拆成多条树链，而两点之间所访问的树链是logn量级，因此给了我们很大的操作空间
• 而一棵树，根据dfn映射到数组上，一条树链就是数组上一段区间。因此我们可以用前缀和、线段树、树状数组等等进行区间操作，区间操作的复杂度也为Ologn（前缀和为O1）

最近练的一些题：（感谢zngg的题）

题1 - [LNOI2014]LCA

链接：https://ac.nowcoder.com/acm/contest/22131/A

题目支持q个询问[l,r]中的结点与z结点的lca的深度之和，即${\sum }_{l\le i\le r}deep[LCA(i,z)]\backslash sum\_\{l\le i\le r\}\; deep[LCA(i,z)]$

思路：很明显，在1≤n≤50000,1≤m≤50000的条件下，在线查询lca的复杂度直接爆炸，因此我们考虑离线（嗯，想到这一步后就gg了）
既然直接查询lca不行，那么我们换一种想法。仔细想想，我们要查的其实并不是lca，而是lca的深度。
我们把 i 到根节点的这条链上权值+1，然后再询问 z 到根节点的链上权值之和，我们会发现，其实这就等于lca的深度。
因此，我们所要做的，就是让 i 从1开始跑，逐个将 i 到根节点的链上权值+1。（相当于做了个前缀和）
那么对于区间 l≤i≤r 来说，最后只需询问当 i=r 时，z 到根节点的链上权值之和，减去当 i=l-1 时，z 到根节点的链上权值之和。

代码：

#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[N];
ll a[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,id,k;}q;
struct tree{ll l,r,tag,sum;}trs[N*4];
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.x;
}
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<qq>v[N];//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 push_up(ll k){
	trs[k].sum=trs[k*2].sum+trs[k*2+1].sum;
}

void push_down(ll k){
	if(trs[k].tag){
		ll l=k*2,r=k*2+1;
		trs[l].tag+=trs[k].tag;
		trs[r].tag+=trs[k].tag;
		trs[l].sum+=(trs[l].r-trs[l].l+1)*trs[k].tag;
		trs[r].sum+=(trs[r].r-trs[r].l+1)*trs[k].tag;
		trs[k].tag=0; 
	}
}

void bd_tree(ll k,ll l,ll r){
	trs[k].tag=0;
	trs[k].l=l,trs[k].r=r;
	if(l==r){
		trs[k].sum=a[l];
		return;
	}
	ll mid=(l+r)/2;
	bd_tree(k*2,l,mid);
	bd_tree(k*2+1,mid+1,r);
	push_up(k);
}

ll query(ll k,ll pl,ll pr){
	ll ml=0,mr=0;
	if(trs[k].l>=pl&&trs[k].r<=pr){
		return trs[k].sum;
	}
	push_down(k);
	ll mid=(trs[k].l+trs[k].r)/2;
	if(mid>=pl)ml=query(k*2,pl,pr);
	if(mid+1<=pr)mr=query(k*2+1,pl,pr);
	return ml+mr;
}

void modify(ll k,ll pl,ll pr,ll val){
	if(trs[k].l>=pl&&trs[k].r<=pr){
		trs[k].sum+=(trs[k].r-trs[k].l+1)*val;
		trs[k].tag+=val;
		return;
	}
	push_down(k);
	ll mid=(trs[k].l+trs[k].r)/2;
	if(mid>=pl)modify(k*2,pl,pr,val);
	if(mid+1<=pr)modify(k*2+1,pl,pr,val);
	push_up(k);
}

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;
	} 
}

void mchain(ll x,ll y,ll val){
	while(tr[x].top!=tr[y].top){
		if(tr[tr[x].top].dep<tr[tr[y].top].dep)modify(1,tr[tr[y].top].dfn,tr[y].dfn,val),y=tr[tr[y].top].fa;
		else modify(1,tr[tr[x].top].dfn,tr[x].dfn,val),x=tr[tr[x].top].fa;
	}
	if(tr[x].dep>tr[y].dep)swap(x,y);
	modify(1,tr[x].dfn,tr[y].dfn,val);
}

ll qchain(ll x,ll y){
	ll res=0;
	while(tr[x].top!=tr[y].top){
		if(tr[tr[x].top].dep<tr[tr[y].top].dep)res+=query(1,tr[tr[y].top].dfn,tr[y].dfn),y=tr[tr[y].top].fa;
		else res+=query(1,tr[tr[x].top].dfn,tr[x].dfn),x=tr[tr[x].top].fa;
	}
	if(tr[x].dep>tr[y].dep)swap(x,y);
	res+=query(1,tr[x].dfn,tr[y].dfn);
	return res;
}

int main(){
	scanf("%lld%lld",&n,&m);
	cnt=0;
	L(i,2,n){
		scanf("%lld",&x);x++;//不喜欢用0做结点，所以全部结点++
		add(x,i,0);
		add(i,x,0);
	}
	tot=0;
	dfs1(1,0);
	dfs2(1,1);
	bd_tree(1,1,n);
	
	L(i,1,m){
		scanf("%lld%lld%lld",&x,&y,&z);
		x++,y++,z++;
		v[x-1].push_back({z,i,-1});
		v[y].push_back({z,i,1});
	}
	
	L(i,1,n){
		mchain(1,i,1);
		ll siz=v[i].size();
		L(j,0,siz-1){
			qq tmp=v[i][j];
			ans[tmp.id]+=tmp.k*qchain(1,tmp.x);
		}
	}
	L(i,1,m){
		printf("%lld\n",ans[i]%201314);
	}
}

题2 - [HAOI2015]树上操作

链接：https://ac.nowcoder.com/acm/contest/22131/B

题目支持3种操作：
操作 1 ：把某个节点 x 的点权增加 a
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和

思路：树链剖分模板题。（a可以是负数，我线段树的板子一直都是tag>0才去push_down，找了半天bug(((φ(◎ロ◎;)φ)))）

代码：

#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,dep,root,block,key,cnt,minn,maxx,ans;
ll a[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*4];
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 push_up(ll k){
	trs[k].sum=trs[k*2].sum+trs[k*2+1].sum;
}

void push_down(ll k){
	if(trs[k].tag>0){
		ll l=k*2,r=k*2+1;
		trs[l].tag+=trs[k].tag;
		trs[r].tag+=trs[k].tag;
		trs[l].sum+=(trs[l].r-trs[l].l+1)*trs[k].tag;
		trs[r].sum+=(trs[r].r-trs[r].l+1)*trs[k].tag;
		trs[k].tag=0; 
	}
}

void bd_tree(ll k,ll l,ll r){
	trs[k].tag=0;
	trs[k].l=l,trs[k].r=r;
	if(l==r){
		trs[k].sum=a[l];
		return;
	}
	ll mid=(l+r)/2;
	bd_tree(k*2,l,mid);
	bd_tree(k*2+1,mid+1,r);
	push_up(k);
}

ll query(ll k,ll pl,ll pr){
	ll ml=0,mr=0;
	if(trs[k].l>=pl&&trs[k].r<=pr){
		return trs[k].sum;
	}
	push_down(k);
	ll mid=(trs[k].l+trs[k].r)/2;
	if(mid>=pl)ml=query(k*2,pl,pr);
	if(mid+1<=pr)mr=query(k*2+1,pl,pr);
	return ml+mr;
}

void modify(ll k,ll pl,ll pr,ll val){//[pl,pr]改为val 
	if(trs[k].l>=pl&&trs[k].r<=pr){
		trs[k].sum+=(trs[k].r-trs[k].l+1)*val;
		trs[k].tag+=val;
		return;
	}
	push_down(k);
	ll mid=(trs[k].l+trs[k].r)/2;
	if(mid>=pl)modify(k*2,pl,pr,val);
	if(mid+1<=pr)modify(k*2+1,pl,pr,val);
	push_up(k);
}

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){
		if(eg[k].to!=ac)dfs1(eg[k].to,x);
		k=eg[k].nxt;
	}
	if(!tr[ac].son||tr[tr[ac].son].siz<tr[x].siz)tr[ac].son=x;
	tr[ac].siz+=tr[x].siz;
	dep--;
}

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

void mchain(ll x,ll y,ll val){
	while(tr[x].top!=tr[y].top){
		if(tr[tr[x].top].dep<tr[tr[y].top].dep)modify(1,tr[tr[y].top].dfn,tr[y].dfn,val),y=tr[tr[y].top].fa;
		else modify(1,tr[tr[x].top].dfn,tr[x].dfn,val),x=tr[tr[x].top].fa;
	}
	if(tr[x].dep>tr[y].dep)swap(x,y);
	modify(1,tr[x].dfn,tr[y].dfn,val);
}

ll qchain(ll x,ll y){
	ll res=0;
	while(tr[x].top!=tr[y].top){
		if(tr[tr[x].top].dep<tr[tr[y].top].dep)res+=query(1,tr[tr[y].top].dfn,tr[y].dfn),y=tr[tr[y].top].fa;
		else res+=query(1,tr[tr[x].top].dfn,tr[x].dfn),x=tr[tr[x].top].fa;
	}
	if(tr[x].dep>tr[y].dep)swap(x,y);
	res+=query(1,tr[x].dfn,tr[y].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);
	}
	num=0;pos=1;
	dfs1(1,0);
	dfs2(1);
	bd_tree(1,1,n);
	//L(i,1,n)printf("%lld ",tr[i].dfn);printf("\n");
	
	L(i,1,m){
		scanf("%lld",&k);
		if(k==1){
			scanf("%lld%lld",&x,&y);
			modify(1,tr[x].dfn,tr[x].dfn,y);
		}
		else if(k==2){
			scanf("%lld%lld",&x,&y);
			modify(1,tr[x].dfn,tr[x].dfn+tr[x].siz-1,y);
		}
		else if(k==3){
			scanf("%lld",&x);
			printf("%lld\n",qchain(1,x));
		}
	}
}

题3 - 树上路径

链接：https://ac.nowcoder.com/acm/contest/22131/C

题目支持3种操作
1.将以u为根的子树内节点(包括u)的权值加val
2.将(u, v)路径上的节点权值加val
3.询问(u, v)路径上节点的权值两两相乘的和

思路：很明显，唯一有难度的就是操作3。
我们换位思考，要计算一个数组内元素两两相乘之和，其实就等于（元素之和的平方-元素平方之和）/2，即对于数组a，求 $[({\sum }_{i=1}^n{a}_i{)}^2-{\sum }_{i=1}^n{a}_i^2]\mathrm{/}2[(\backslash sum\_\{i=1\}^n\; a\_i)^2-\backslash sum\_\{i=1\}^n\; a\_i^2]/2$。
因此我们不仅要维护区间和，还要维护区间内元素平方之和，特别推导一下修改时平方和的变化即可。

代码：

#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=1e9+7,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],head[N],dx[5]={0,0,-1,1},dy[5]={-1,1,0,0};
double dans;
bool vis,flag;
char mapp,zz[20];
struct qq{ll x,y;}q;
struct tree{ll l,r,tag,sum,mul;}trs[N*4];
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.x;
}
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序

ll two=fksm(2,mod-2);
pair<ll,ll>pre;
vector<qq>v[N];//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 push_up(ll k){
	trs[k].sum=trs[k*2].sum+trs[k*2+1].sum;trs[k].sum%=mod;
	trs[k].mul=trs[k*2].mul+trs[k*2+1].mul;trs[k].mul%=mod;
}

void push_down(ll k){
	if(trs[k].tag){
		ll l=k*2,r=k*2+1;
		ll lenl=trs[l].r-trs[l].l+1,lenr=trs[r].r-trs[r].l+1;
		trs[l].tag+=trs[k].tag;trs[l].tag%=mod;
		trs[r].tag+=trs[k].tag;trs[r].tag%=mod;
		trs[l].mul+=2*trs[l].sum*trs[k].tag%mod+lenl*trs[k].tag%mod*trs[k].tag%mod;trs[l].mul%=mod;
		trs[r].mul+=2*trs[r].sum*trs[k].tag%mod+lenr*trs[k].tag%mod*trs[k].tag%mod;trs[r].mul%=mod;
		trs[l].sum+=lenl*trs[k].tag%mod;trs[l].sum%=mod;
		trs[r].sum+=lenr*trs[k].tag%mod;trs[r].sum%=mod;
		trs[k].tag=0; 
	}
}

void bd_tree(ll k,ll l,ll r){
	trs[k].tag=0;
	trs[k].l=l,trs[k].r=r;
	if(l==r){
		trs[k].sum=a[l]%mod;
		trs[k].mul=a[l]*a[l]%mod;
		return;
	}
	ll mid=(l+r)/2;
	bd_tree(k*2,l,mid);
	bd_tree(k*2+1,mid+1,r);
	push_up(k);
}

qq query(ll k,ll pl,ll pr){
	qq ml={0,0},mr={0,0};
	if(trs[k].l>=pl&&trs[k].r<=pr){
		return {trs[k].sum,trs[k].mul};
	}
	push_down(k);
	ll mid=(trs[k].l+trs[k].r)/2;
	if(mid>=pl)ml=query(k*2,pl,pr);
	if(mid+1<=pr)mr=query(k*2+1,pl,pr);
	return {(ml.x+mr.x)%mod,(ml.y+mr.y)%mod};
}

void modify(ll k,ll pl,ll pr,ll val){//[pl,pr]改为val 
	if(trs[k].l>=pl&&trs[k].r<=pr){
		trs[k].mul+=2*trs[k].sum*val%mod+(trs[k].r-trs[k].l+1)*val%mod*val%mod;trs[k].mul%=mod;
		trs[k].sum+=(trs[k].r-trs[k].l+1)*val%mod;trs[k].sum%=mod;
		trs[k].tag+=val;trs[k].tag%=mod;
		return;
	}
	push_down(k);
	ll mid=(trs[k].l+trs[k].r)/2;
	if(mid>=pl)modify(k*2,pl,pr,val);
	if(mid+1<=pr)modify(k*2+1,pl,pr,val);
	push_up(k);
}

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;
	} 
}

void mchain(ll x,ll y,ll val){
	while(tr[x].top!=tr[y].top){
		if(tr[tr[x].top].dep<tr[tr[y].top].dep)modify(1,tr[tr[y].top].dfn,tr[y].dfn,val),y=tr[tr[y].top].fa;
		else modify(1,tr[tr[x].top].dfn,tr[x].dfn,val),x=tr[tr[x].top].fa;
	}
	if(tr[x].dep>tr[y].dep)swap(x,y);
	modify(1,tr[x].dfn,tr[y].dfn,val);
}

qq qchain(ll x,ll y){
	qq res={0,0},tmp;
	while(tr[x].top!=tr[y].top){
		if(tr[tr[x].top].dep<tr[tr[y].top].dep)tmp=query(1,tr[tr[y].top].dfn,tr[y].dfn),y=tr[tr[y].top].fa;
		else tmp=query(1,tr[tr[x].top].dfn,tr[x].dfn),x=tr[tr[x].top].fa;
		res={(res.x+tmp.x)%mod,(res.y+tmp.y)%mod};
	}
	if(tr[x].dep>tr[y].dep)swap(x,y);
	tmp=query(1,tr[x].dfn,tr[y].dfn);
	res={(res.x+tmp.x)%mod,(res.y+tmp.y)%mod};
	return res;
}

int main(){
	scanf("%lld%lld",&n,&m);
	L(i,1,n)scanf("%lld",&tr[i].w);
	cnt=0;
	L(i,2,n){
		scanf("%lld%lld",&x,&y);
		add(x,y,0);
		add(y,x,0);
	}
	tot=0;
	dfs1(1,0);
	dfs2(1,1);
	bd_tree(1,1,n);
	//L(i,1,n)printf("%lld ",tr[i].dfn);printf("\n");
	
	L(i,1,m){
		scanf("%lld",&k);
		if(k==1){
			scanf("%lld%lld",&x,&y);
			modify(1,tr[x].dfn,tr[x].dfn+tr[x].siz-1,y);
		}
		else if(k==2){
			scanf("%lld%lld%lld",&x,&y,&z);
			mchain(x,y,z);
		}
		else{
			scanf("%lld%lld",&x,&y);
			qq tmp=qchain(x,y);
			ans=(tmp.x*tmp.x%mod-tmp.y+mod)%mod*two%mod;
			printf("%lld\n",ans);
		}
	}
}

题4 - 软件包管理器

链接：https://ac.nowcoder.com/acm/contest/22131/D

题目一堆废话，概括一下就是支持两种操作：
1、将 x 到根节点的链上权值改为1
2、将以 x 为根节点的子树中结点权值改为0
在每次操作后询问具体更改了几个权值（0改为0或1改为1不算）

思路：理解题目意思后就会发现，还是一道模板题

代码：

#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],head[N],dx[5]={0,0,-1,1},dy[5]={-1,1,0,0};
double dans;
bool vis,flag;
char mapp,zz[20];
struct qq{ll x,id,k;}q;
struct tree{ll l,r,tag,sum;}trs[N*4];
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.x;
}
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<qq>v[N];//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 push_up(ll k){
	trs[k].sum=trs[k*2].sum+trs[k*2+1].sum;
}

void push_down(ll k){
	if(trs[k].tag>=0){
		ll l=k*2,r=k*2+1;
		trs[l].tag=trs[k].tag;
		trs[r].tag=trs[k].tag;
		trs[l].sum=(trs[l].r-trs[l].l+1)*trs[k].tag;
		trs[r].sum=(trs[r].r-trs[r].l+1)*trs[k].tag;
		trs[k].tag=-1; 
	}
}

void bd_tree(ll k,ll l,ll r){
	trs[k].tag=-1;
	trs[k].l=l,trs[k].r=r;
	if(l==r){
		trs[k].sum=0;
		return;
	}
	ll mid=(l+r)/2;
	bd_tree(k*2,l,mid);
	bd_tree(k*2+1,mid+1,r);
	push_up(k);
}

ll query(ll k,ll pl,ll pr){
	ll ml=0,mr=0;
	if(trs[k].l>=pl&&trs[k].r<=pr){
		return trs[k].sum;
	}
	push_down(k);
	ll mid=(trs[k].l+trs[k].r)/2;
	if(mid>=pl)ml=query(k*2,pl,pr);
	if(mid+1<=pr)mr=query(k*2+1,pl,pr);
	return ml+mr;
}

void modify(ll k,ll pl,ll pr,ll val){//[pl,pr]改为val 
	if(trs[k].l>=pl&&trs[k].r<=pr){
		trs[k].sum=(trs[k].r-trs[k].l+1)*val;
		trs[k].tag=val;
		return;
	}
	push_down(k);
	ll mid=(trs[k].l+trs[k].r)/2;
	if(mid>=pl)modify(k*2,pl,pr,val);
	if(mid+1<=pr)modify(k*2+1,pl,pr,val);
	push_up(k);
}

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;
	} 
}

void mchain(ll x,ll y,ll val){
	while(tr[x].top!=tr[y].top){
		if(tr[tr[x].top].dep<tr[tr[y].top].dep)modify(1,tr[tr[y].top].dfn,tr[y].dfn,val),y=tr[tr[y].top].fa;
		else modify(1,tr[tr[x].top].dfn,tr[x].dfn,val),x=tr[tr[x].top].fa;
	}
	if(tr[x].dep>tr[y].dep)swap(x,y);
	modify(1,tr[x].dfn,tr[y].dfn,val);
}

ll qchain(ll x,ll y){
	ll res=0;
	while(tr[x].top!=tr[y].top){
		if(tr[tr[x].top].dep<tr[tr[y].top].dep)res+=query(1,tr[tr[y].top].dfn,tr[y].dfn),y=tr[tr[y].top].fa;
		else res+=query(1,tr[tr[x].top].dfn,tr[x].dfn),x=tr[tr[x].top].fa;
	}
	if(tr[x].dep>tr[y].dep)swap(x,y);
	res+=query(1,tr[x].dfn,tr[y].dfn);
	return res;
}

int main(){
	scanf("%lld",&n);
	cnt=0;
	L(i,2,n){
		scanf("%lld",&x);x++;
		add(x,i,0);
		add(i,x,0);
	}
	tot=0;
	dfs1(1,0);
	dfs2(1,1);
	bd_tree(1,1,n);
	//L(i,1,n)printf("%lld ",tr[i].dfn);printf("\n");
	
	scanf("%lld",&m);
	L(i,1,m){
		scanf("%s%lld",zz,&x);x++;
		if(zz[0]=='i'){
			l=qchain(1,x);
			mchain(1,x,1);
			r=qchain(1,x);
			printf("%lld\n",r-l);
		}
		else{
			printf("%lld\n",query(1,tr[x].dfn,tr[x].dfn+tr[x].siz-1));
			modify(1,tr[x].dfn,tr[x].dfn+tr[x].siz-1,0);
		}
	}
}

题5 - [JLOI2014]松鼠的新家

链接：https://ac.nowcoder.com/acm/contest/22131/E

给定一棵树的路径关系，给定一个访问结点的顺序，同时每经过一次结点，结点权值+1，对于最后一个访问的结点不用+1。最后询问每一个结点的权值。

思路：对于从x结点去y结点，只需将x到y的链上权值+1，同时对y结点权值-1即可，模板题。

代码：

#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],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*4];
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 push_up(ll k){
	trs[k].sum=trs[k*2].sum+trs[k*2+1].sum;
}

void push_down(ll k){
	if(trs[k].tag){
		ll l=k*2,r=k*2+1;
		trs[l].tag+=trs[k].tag;
		trs[r].tag+=trs[k].tag;
		trs[l].sum+=(trs[l].r-trs[l].l+1)*trs[k].tag;
		trs[r].sum+=(trs[r].r-trs[r].l+1)*trs[k].tag;
		trs[k].tag=0; 
	}
}

void bd_tree(ll k,ll l,ll r){
	trs[k].tag=0;
	trs[k].l=l,trs[k].r=r;
	if(l==r){
		trs[k].sum=a[l];
		return;
	}
	ll mid=(l+r)/2;
	bd_tree(k*2,l,mid);
	bd_tree(k*2+1,mid+1,r);
	push_up(k);
}

ll query(ll k,ll pl,ll pr){
	ll ml=0,mr=0;
	if(trs[k].l>=pl&&trs[k].r<=pr){
		return trs[k].sum;
	}
	push_down(k);
	ll mid=(trs[k].l+trs[k].r)/2;
	if(mid>=pl)ml=query(k*2,pl,pr);
	if(mid+1<=pr)mr=query(k*2+1,pl,pr);
	return ml+mr;
}

void modify(ll k,ll pl,ll pr,ll val){//[pl,pr]改为val 
	if(trs[k].l>=pl&&trs[k].r<=pr){
		trs[k].sum+=(trs[k].r-trs[k].l+1)*val;
		trs[k].tag+=val;
		return;
	}
	push_down(k);
	ll mid=(trs[k].l+trs[k].r)/2;
	if(mid>=pl)modify(k*2,pl,pr,val);
	if(mid+1<=pr)modify(k*2+1,pl,pr,val);
	push_up(k);
}

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;
	} 
}

void mchain(ll x,ll y,ll val){
	while(tr[x].top!=tr[y].top){
		if(tr[tr[x].top].dep<tr[tr[y].top].dep)modify(1,tr[tr[y].top].dfn,tr[y].dfn,val),y=tr[tr[y].top].fa;
		else modify(1,tr[tr[x].top].dfn,tr[x].dfn,val),x=tr[tr[x].top].fa;
	}
	if(tr[x].dep>tr[y].dep)swap(x,y);
	modify(1,tr[x].dfn,tr[y].dfn,val);
}

ll qchain(ll x,ll y){
	ll res=0;
	while(tr[x].top!=tr[y].top){
		if(tr[tr[x].top].dep<tr[tr[y].top].dep)res+=query(1,tr[tr[y].top].dfn,tr[y].dfn),y=tr[tr[y].top].fa;
		else res+=query(1,tr[tr[x].top].dfn,tr[x].dfn),x=tr[tr[x].top].fa;
	}
	if(tr[x].dep>tr[y].dep)swap(x,y);
	res+=query(1,tr[x].dfn,tr[y].dfn);
	return res;
}

int main(){
	scanf("%lld",&n);
	L(i,1,n)scanf("%lld",&b[i]);
	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);
	bd_tree(1,1,n);
	//L(i,1,n)printf("%lld ",tr[i].dfn);printf("\n");
	
	L(i,2,n){
		mchain(b[i-1],b[i],1);
		modify(1,tr[b[i]].dfn,tr[b[i]].dfn,-1);
	}
	L(i,1,n){
		printf("%lld\n",query(1,tr[i].dfn,tr[i].dfn));
	}
}

题6 - 小沙的身法

寒假训练营2的一道题
链接：https://ac.nowcoder.com/acm/contest/23477/G

给定一棵树的路径关系，每个结点有一个高度，从低到高需要花费它俩高度之差的体力。有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));
	}
}