长剖re求调
查看原帖
长剖re求调
1026365
yb_10032楼主2025/1/11 11:32
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=1e6+10;
struct Edge{
	ll to,next;
}e[N<<1];
ll head[N],idx;
inline void add(ll u,ll v){
	e[++idx]={v,head[u]};
	head[u]=idx;
}
ll n;
ll h[N],lson[N];
ll *f[N],*now=lson;
ll ans[N];
inline void dfs_son(ll u,ll fa){
	for(ll i=head[u];i;i=e[i].next){
		ll v=e[i].to;
		if(v==fa)
			continue;
		dfs_son(v,u);
		if(h[v]>h[lson[u]])
			lson[u]=v;
	}
	h[u]=h[lson[u]]+1;
}
inline void dfs(ll u,ll fa){
	f[u][0]=1;
	if(lson[u]){
		f[lson[u]]=f[u]+1;
		dfs(lson[u],u);
	}
	ans[u]=ans[lson[u]]+1;
	for(ll i=head[u];i;i=e[i].next){
		ll v=e[i].to;
		if(v==fa||v==lson[u])
			continue;
		f[v]=now,now+=h[v];
		dfs(v,u);
		for(int j=1;j<=h[v];j++){
			f[u][j]+=f[v][j-1];
			if(f[u][j]>f[u][ans[u]]||(f[u][j]==f[u][ans[u]]&&j<ans[u]))
				ans[u]=j;
		}
	}
}
int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin>>n;
    for(ll i=1;i<=n-1;i++){
    	ll u,v;
    	cin>>u>>v;
    	add(u,v);
    	add(v,u);
	}
	dfs_son(1,0);
	f[1]=now,now+=h[1];
	dfs(1,0);
	for(ll i=1;i<=n;i++)
		cout<<(f[i][ans[i]]==1?0:ans[i])<<endl;
    return 0;
}
2025/1/11 11:32
加载中...