cjwdxfblzs @ 2023-09-08 20:13:07
本人非常不精通指针 所以用vector倒序存储dp数组 这样也许可以不用指针 但是MLE了 想知道问题所在
```cpp
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1000050,M = 2000050;
int e[M],ne[M],h[N],idx;
int mx[N],mc[N],c,d;
vector<int> v[N];
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int dep[N],md[N],f[N],son[N],top[N];
void dfs1(int u,int fa){
md[u]=1;
for(int i = h[u];~i;i = ne[i]){
int j = e[i];
if(j==fa)continue;
dep[j]=dep[u]+1;
f[j]=u;
dfs1(j,u);
if(md[j]>md[son[u]])son[u]=j;
md[u]=max(md[u],md[j]+1);
}
}
void dfs2(int u,int tp){
top[u]=tp;
if(son[u])dfs2(son[u],tp);
for(int i = h[u];~i;i = ne[i]){
int j = e[i];
if(j==son[u]||j==f[u])continue;
dfs2(j,j);
}
}
void dp(int u,int fa){
for(int i = h[u];~i;i = ne[i]){
int j = e[i];
if(j==fa)continue;
dp(j,u);
}
v[u]=v[son[u]];
v[son[u]].clear();
mc[u]=mc[son[u]];
mx[u]=mx[son[u]]+1;
for(int i = h[u];~i;i = ne[i]){
int j = e[i];
if(j==fa||j==son[u])continue;
int now = v[u].size()-1;
while(!v[j].empty()){
int p = v[j].back();
v[u][now]+=p;
v[j].pop_back();
if(v[u][now]>mc[u]||(v[u][now]==mc[u]&&mx[u]>v[u].size()-now)){
mc[u]=v[u][now];
mx[u]=v[u].size()-now;
}
now--;
}
}
v[u].push_back(1);
if(1>mc[u]||(1==mc[u]&&mx[u]>0)){
mc[u]=1;
mx[u]=0;
}
}
inline int read(){
int x=0;
char c = getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){
x=x*10+c-48;
c=getchar();
}
return x;
}
int main(){
memset(h,-1,sizeof h);
n=read();
for(int i = 1;i < n;i++){
int a=read(),b=read();
if(i==1)c=a,d=b;
add(a,b);
add(b,a);
}
dfs1(1,-1);
dfs2(1,1);
dp(1,-1);
for(int i = 1;i <= n;i++)printf("%d\n",mx[i]);
return 0;
}
```