警钟长鸣
查看原帖
警钟长鸣
813622
Igallta楼主2024/1/4 16:36

如果你WA 25pts

请看你的b数组开对没有(要开2*N)

#include<bits/stdc++.h>
#define int long long
#define lg log2
using namespace std;
const int N=4e5+1;
int n,m,fa[N],w[N],dep[N],LCA[N],b1[N*2],b2[N*2],t1,t2,cs[N],st[N],ed[N],ans[N],lca[N];
bool vis[N],pis[N];
vector<int>vec[N];
vector<pair<int,int>>querye[N],querys[N],querylca[N];
int getfa(int x){return (fa[x]==x?x:fa[x]=getfa(fa[x]));}
void tarjan(int u,int deep){
	vis[u]=1;
	dep[u]=deep;
	fa[u]=u;
//	cout<<"u="<<u<<" deep="<<deep<<'\n';
	for(auto v:vec[u]){
		if(!vis[v]){
			tarjan(v,deep+1);
			fa[v]=u;
		}
	}
	for(auto k:querys[u]){
		int r=k.first,i=k.second;
		if(vis[r]){
			lca[i]=getfa(r);
		}
	}
	for(auto k:querye[u]){
		int r=k.first,i=k.second;
		if(vis[r]){
			lca[i]=getfa(r);
		}
	}
}
void dfs(int i){
	int t1=b1[w[i]+dep[i]],t2=b2[w[i]-dep[i]+N];
	vis[i]=1;
	for(auto v:vec[i]){
		if(!vis[v]){
			dfs(v);
		}
	}
	b1[dep[i]]+=querys[i].size();
//	cout<<"u="<<i<<":u为起点的个数"<<querys[i].size()<<'\n';
	for(auto q:querye[i]){
		int u=q.first,k=q.second;
		b2[dep[u]-dep[lca[k]]*2+N]++;
	} 
	ans[i]+=(b1[w[i]+dep[i]]+b2[w[i]-dep[i]+N]-t1-t2);
//	cout<<"第"<<i<<"个当前结果:"<<ans[i]<<'\n';
	for(auto q:querylca[i]){
		int k=q.second;
		b1[dep[st[k]]]--;
		b2[dep[st[k]]-2*dep[lca[k]]+N]--;
	}
}
signed main(){
//	freopen("P1600_1.in","r",stdin);
//	freopen("my.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin>>u>>v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=m;i++){
		cin>>st[i]>>ed[i];
		querys[st[i]].push_back({ed[i],i});
		querye[ed[i]].push_back({st[i],i});
	}
	tarjan(1,1);
	for(int i=1;i<=m;i++){
//		cout<<lca[i]<<endl;
		querylca[lca[i]].push_back({st[i],i});
		if(dep[st[i]]==w[lca[i]]+dep[lca[i]])ans[lca[i]]--;
	}
	memset(vis,0,sizeof vis);
	dfs(1);
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<' ';
	}
	return 0;
}

2024/1/4 16:36
加载中...