悬关,码风清新,MnZn刚学 OI 0.00000001秒,30分求调
查看原帖
悬关,码风清新,MnZn刚学 OI 0.00000001秒,30分求调
826079
Autumn_Rain楼主2024/7/30 16:51

标题党,帮忙调一下吧。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,u,v;
struct node{
	int nxt,to;
}e[N],e1[N],e2[N];
int h[N],cnt;
void add(int u,int v){
	e[++cnt].nxt=h[u];
	e[cnt].to=v;
	h[u]=cnt;
}
int h1[N],cnt1;
void add1(int u,int v){
	e1[++cnt1].nxt=h1[u];
	e1[cnt1].to=v;
	h1[u]=cnt1;
}
int h2[N],cnt2;
void add2(int u,int v){
	e2[++cnt2].nxt=h2[u];
	e2[cnt2].to=v;
	h2[u]=cnt2;
}
int w[N],sz[N];//子树大小,深度 

//LCA
int anc[N][30],d[N];
void dfs(int u,int fa){
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)continue;
		d[v]=d[u]+1;
		anc[v][0]=u;
		dfs(v,u);
	}
}
void init(){
	for(int j=1;j<=20;j++){
		for(int i=1;i<=n;i++){
			anc[i][j]=anc[anc[i][j-1]][j-1];
		}
	}
}
int lca(int u,int v){
	if(d[u]<d[v])swap(u,v);
	for(int i=20;i>=0;i--){
		if(d[anc[u][i]]>=d[v]){
			u=anc[u][i];
		}
	}
	if(u==v)return u;
	for(int i=20;i>=0;i--){
		if(anc[u][i]!=anc[v][i]){
			u=anc[u][i];
			v=anc[v][i];
		}
	}
	return anc[u][0];
}
//LCA
int bg[N];//以每个结点作为起点的路径条数
int dis[N],s[N],t[N];
int ans[N];
int t1[N],t2[N];

void dfs2(int u,int fa){
	int T1=t1[w[u]+d[u]];
	int T2=t2[w[u]-d[u]+N];//平移
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)continue;
		dfs2(v,u);
	}
	t1[d[u]]+=bg[u];
	for(int i=h1[u];i;i=e1[i].nxt){
		int v=e1[i].to;
		t2[dis[v]-d[t[v]]+N]++;
	}
	ans[u]+=t1[w[u]+d[u]]-T1+t2[w[u]-d[u]+N]-T2;
	for(int i=h2[u];i;i=e2[i].nxt){
		int v=e2[i].to;
		t1[d[s[v]]]--;
		t2[dis[v]-d[t[v]]+N]--;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	d[1]=1;
	dfs(1,0);
	init();
	for(int i=1;i<=m;i++){
		cin>>s[i]>>t[i];
		int f=lca(s[i],t[i]);
		dis[i]=d[s[i]]+d[t[i]]-2*d[f];
		bg[s[i]]++;
		add1(t[i],i);
		add2(f,i);
		if(d[f]+w[f]==d[s[i]]){
			ans[f]--;//重复 
		}
	}
	dfs2(1,0);
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	return 0;
}
2024/7/30 16:51
加载中...