天天爱跑步求条
  • 板块灌水区
  • 楼主zhx20081129
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/5 18:34
  • 上次更新2024/8/5 19:34:40
查看原帖
天天爱跑步求条
914572
zhx20081129楼主2024/8/5 18:34
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+7;
struct T{
	int v,nex;
}e[N<<1];
struct P{
	int d,tmp;
};
int n,m,head[N],f[N][25],dep[N],ans[N],anc[N],cnt,w[N],s[N],t[N],buk1[N],buk2[N<<1];
vector<P>op1[N],op2[N];
void dfs(int u,int fa){
	dep[u]=dep[fa]+1;f[u][0]=fa;
	for(int i=1;f[u][i-1];i++)f[u][i]=f[f[u][i-1]][i-1]; 
	for(int i=head[u];i;i=e[i].nex){
		int v=e[i].v;
		if(v==fa)continue;
		dfs(v,u);
	}
} 
void add(int u,int v){
	e[++cnt]={v,head[u]};
	head[u]=cnt;
} 
void init(){
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		add(u,v);add(v,u);
	}
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=m;i++)cin>>s[i]>>t[i];
	dfs(1,0); 
}
int LCA(int u,int v){
	if(dep[u]>dep[v])swap(u,v);
	for(int i=22;i>=0;i--){
		if(dep[u]<=dep[v]-(1<<i))v=f[v][i];
	} 
	if(u==v)return u;
	for(int i=22;i>=0;i--){
		if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
	}
	return f[u][0];
}
void dfs(int u){
	int xx=buk1[dep[u]+w[u]];
	for(int i=head[u];i;i=e[i].nex){
		int v=e[i].v;
		if(v==f[u][0])continue;
		dfs(v);
	}
	for(int i=0;i<op1[u].size();i++)buk1[op1[u][i].d]+=op1[u][i].tmp;
	int yy=buk1[dep[u]+w[u]];
	ans[u]+=yy-xx;
}
void work_up(){
	for(int i=1;i<=m;i++){
		anc[i]=LCA(s[i],t[i]);
		op1[s[i]].push_back({dep[s[i]],1});
		op1[anc[i]].push_back({dep[s[i]],-1}); 
	}
	dfs(1);
}
void dfs2(int u){
	int xx=buk2[w[u]-dep[u]+N];
	for(int i=head[u];i;i=e[i].nex){
		if(e[i].v==f[u][0])continue;
		dfs2(e[i].v);
	}
	for(int i=0;i<op2[u].size();i++)buk2[op2[u][i].d+N]+=op2[u][i].tmp;
	int yy=buk2[w[u]-dep[u]+N];
	ans[u]+=yy-xx;
}
void work_down(){
	for(int i=1;i<=m;i++){
		int dist=dep[s[i]+dep[t[i]]]-2*dep[anc[i]];
		op2[t[i]].push_back({dist-dep[t[i]],1});
		if(f[anc[i]][0])op2[f[anc[i]][0]].push_back({dist-dep[t[i]],-1});
	}
	dfs2(1);
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	init();
	work_up();
	work_down();
	for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
	return 0;
} 
2024/8/5 18:34
加载中...