【树上差分】[JLOI2014] 松鼠的新家

绝地灬酷狼 2024-03-17 10:57 85阅读 0赞

[N-\[JLOI2014\]松鼠的新家\_2021秋季算法入门班第十三章习题：LCA (nowcoder.com)][N-_JLOI2014_2021_LCA _nowcoder.com]

题意：  
![0e6d1c4ba2af48c796a4ad7c53361376.png][]

思路：

给u到v的路径中的所有结点都+val

裸的树上差分，给单点打标记，最后求个后缀和就行

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=3e5+10;
    const int mxe=3e5+10;
    
    struct ty{
    	int to,next;
    }edge[mxe<<2];
    
    int N,u,v,tot=0;
    int a[mxn],b[mxn];
    int head[mxn],dep[mxn],F[mxn][33];
    
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	tot=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    	}
    }
    void dfs(int u,int fa){
    	dep[u]=dep[fa]+1;
    	F[u][0]=fa;
    	for(int j=1;j<=30;j++) F[u][j]=F[F[u][j-1]][j-1];
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		dfs(edge[i].to,u);
    	}
    }
    int lca(int u,int v){
    	if(dep[u]<dep[v]) swap(u,v);
    	for(int j=30;j>=0;j--){
    		if(dep[F[u][j]]>=dep[v]){
    			u=F[u][j];
    		}
    	}
    	if(u==v) return u;
    	for(int j=30;j>=0;j--){
    		if(F[u][j]!=F[v][j]){
    			u=F[u][j];
    			v=F[v][j];
    		}
    	}
    	return F[u][0];
    }
    void dfs2(int u,int fa){
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		dfs2(edge[i].to,u);
    		b[u]+=b[edge[i].to];
    	}
    }
    void solve(){
    	cin>>N;
    	G_init();
    	for(int i=1;i<=N;i++) cin>>a[i];
    	for(int i=1;i<=N-1;i++){
    		cin>>u>>v;
    		add(u,v);
    		add(v,u);
    	}
    	dfs(1,0);
    	for(int i=2;i<=N;i++){
    		int u=a[i-1];
    		int v=a[i];
    		int t=lca(u,v);
    		b[F[t][0]]--;
    		b[t]--;
    		b[u]++;
    		b[v]++;
    	}
    	dfs2(1,0);
    	for(int i=2;i<=N;i++) b[a[i]]--;
    	for(int i=1;i<=N;i++) cout<<b[i]<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[N-_JLOI2014_2021_LCA _nowcoder.com]: https://ac.nowcoder.com/acm/contest/27836/N
[0e6d1c4ba2af48c796a4ad7c53361376.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/f2361196af494da9a068710cb677f479.png