dsu-on-tree,双端队列
题意
给定一棵有 \(n\) 个顶点的有根树，以顶点 \(1\) 作为根。
定义顶点 \(x\) 的深度数组为一个无限序列 \([d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]\)，其中 \(d_{x, i}\) 表示满足以下两个条件的顶点 \(y\) 的数量：
- \(x\) 是 \(y\) 的祖先；
- 从 \(x\) 到 \(y\) 的简单路径恰好经过 \(i\) 条边。
对于每个 \(x\)，求 \(\max d_{x,i}\)。
\(1 \le n \le 10^6\)
题解
考虑对于节点 \(u\) 的儿子 \(v\)，在 \(d_v\) 的前面插入一个 \(0\) 就是其对 \(u\) 的贡献。
用 deque 维护，dsu-on-tree 暴力更新即可，时间复杂度 \(O(n\log n)\)，常数可能会比较大。
代码
#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int Maxn=1e6+10;
vector<int>edge[Maxn];
int sz[Maxn],h[Maxn];
int ans[Maxn];
int n;
void dfs1(int u,int fa=0)
{sz[u]=1;for(int v:edge[u]) if(v!=fa){dfs1(v,u);if(sz[v]>sz[h[u]]) h[u]=v;sz[u]+=sz[v];}
}
deque<int>dfs2(int u,int fa=0)
{if(!h[u]){deque<int>re;re.push_front(1);return re;}deque<int>q=dfs2(h[u],u);q.push_front(1);ans[u]=ans[h[u]]+1;if(q[0]>=q[ans[u]]) ans[u]=0;for(int v:edge[u]) if(v!=fa && v!=h[u]){deque<int>tmp=dfs2(v,u);tmp.push_front(0);while(q.size()<tmp.size()) q.push_back(0);for(int j=0;j<tmp.size();j++){q[j]+=tmp[j];if(q[j]>q[ans[u]] || (j<ans[u] && q[j]==q[ans[u]])) ans[u]=j;}}return q;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;edge[u].push_back(v);edge[v].push_back(u);}dfs1(1);dfs2(1);for(int i=1;i<=n;i++) cout<<ans[i]<<endl;return 0;
}