Dominant Indices
这个题显然可以启发式合并做掉。
时间复杂度是 $O(n\log n)$ 的。
满足于这个题肯定已经够了，但还有更快的方法：长链剖分。
长链剖分，顾名思义就是找到每个点的长儿子（深度最深），把整棵树剖成长链。
OI wiki 上有讲，这种方法的跳链一类的复杂度是 $O(\sqrt{n})$ 级别的，而且能卡。
但我们这题显然不是利用这个性质。
我们有一个最简单的 DP。
定义 $f(p,j)$ 表示离节点 $p$ 距离为 $j$ 的节点个数，则有：
$$f(p,j)=\sum_{v}f(v,j-1)$$
特别的，我们有初始化：
$$f(p,0)=1$$
即距离为 $0$ 的节点只有 $p$ 自己。
我们发现这个转移的瓶颈在于每个节点都要 $O(n)$ 的合并。
然后我们就想到一个偷懒的方法，那就是根本不去合并，而是把长儿子的答案直接存在自己的答案里，然后把非长儿子的信息暴力合并进来。
可能刚听到这个想法大部分人反应不过来，实际上这是一个用指针动态分配内存的操作。直接叙述实际上稍显累赘，看代码的话会更为清晰（只可意会不可言传）。
比如说，我们开一串数组，给下面的动态分配内存留下一个池子。
接着我们给 $p$ 分配一个长度为 $dep(p)$ 的内存空间。在这个空间上，我们直接把 $p$ 的长儿子的答案存在这段空间的上，不过对应的下标要错开一位。
接着，我们把非长儿子的答案暴力合并，也就是去做上述的 DP。
可能在直觉上，很多人觉得这个方法的复杂度大概还是 $O(n^2)$ 级别的。
但实际上，这个优化把空间和时间复杂度全部优化到了 $O(n)$ 级别。
先说时间上，我们真正的复杂度开销全在暴力合并这一个环节上。我们不从 $p$ 考虑，而去从它的非长儿子考虑。每个点会被暴力合并，当且仅当它是一个非长儿子，即它是一条长链的顶点。那么时间复杂度就与长链数线性相关。而长链数是 $O(n)$ 级别的（我这里说的是严格的 $O$ 而不是 $\Theta$，因为从这个角度来考虑，我们的开销就全在长儿子的计算上了，而长儿子的计算显然是 $\Theta(n)$ 的）。
那么接下来看空间，我们相当于给每个长链申请了一片大小为长链长度的内存，所以最后所需的内存大小即为树的大小，空间复杂度也是 $O(n)$ 的。
至此，这道题目得到了 $O(n)$ 的解决。
代码（长链剖分优化）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=1e6;
ll n,u,v,tot;
ll buf[N+5];
ll *f[N+5],*now=buf;
ll ver[N*2+5],nxt[N*2+5],head[N+5];
ll ans[N+5],dep[N+5],ls[N+5];
inline void dfs(ll p,ll fath) {
for(ll i=head[p];i;i=nxt[i]) {
if(ver[i]==fath) continue;
dfs(ver[i],p);
if(dep[ver[i]]>dep[ls[p]]) ls[p]=ver[i];
}
dep[p]=dep[ls[p]]+1;
}
inline void dfs_(ll p,ll fath) {
f[p][0]=1;
if(ls[p]) {
f[ls[p]]=f[p]+1;
dfs_(ls[p],p);
ans[p]=ans[ls[p]]+1;
}
for(ll i=head[p];i;i=nxt[i]) {
if(ver[i]==fath||ver[i]==ls[p]) continue;
f[ver[i]]=now;now+=dep[ver[i]];
dfs_(ver[i],p);
for(ll j=1;j<=dep[ver[i]];j++) {
f[p][j]+=f[ver[i]][j-1];
if(f[p][j]>f[p][ans[p]]||(f[p][j]==f[p][ans[p]]&&j<ans[p])) ans[p]=j;
}
}
if(f[p][ans[p]]==1) ans[p]=0;
}
inline void addedge(ll u,ll v) {
ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {
do{buf[++len]=x%10+48;x/=10;}while(x);
}
else {
putchar('-');
do{buf[++len]=-(x%10)+48;x/=10;}while(x);
}
while(len>=0) putchar(buf[len--]);
}
inline void writeln(ll x) {
write(x);putchar('\n');
}
int main() {
n=read();
for(ll i=1;i<n;i++) {
u=read();v=read();
addedge(u,v);addedge(v,u);
}
dfs(1,0);
f[1]=now;now+=dep[1];
dfs_(1,0);
for(ll i=1;i<=n;i++) {writeln(ans[i]);}
return 0;
}
|
代码（启发式合并）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=1e6;
ll n,u,v,tot,tmpans;
ll siz[N+5],dt[N+5],hs[N+5],ans[N+5],cnt[N+5];
ll ver[N*2+5],nxt[N*2+5],head[N+5];
inline void dfs(ll p,ll fath) {
siz[p]=1;dt[p]=dt[fath]+1;
for(ll i=head[p];i;i=nxt[i]) {
if(ver[i]==fath) continue;
dfs(ver[i],p);
if(siz[ver[i]]>siz[hs[p]]) hs[p]=ver[i];
siz[p]+=siz[ver[i]];
}
}
inline void getans(ll p,ll fath) {
cnt[dt[p]]++;
if(cnt[dt[p]]>cnt[tmpans]) tmpans=dt[p];
else if(cnt[dt[p]]==cnt[tmpans]&&dt[p]<tmpans) tmpans=dt[p];
for(ll i=head[p];i;i=nxt[i]) {
if(ver[i]==fath) continue;
getans(ver[i],p);
}
}
inline void clear(ll p,ll fath) {
cnt[dt[p]]--;
for(ll i=head[p];i;i=nxt[i]) {
if(ver[i]==fath) continue;
clear(ver[i],p);
}
}
inline void dfs_(ll p,ll fath,bool kp) {
for(ll i=head[p];i;i=nxt[i]) {
if(ver[i]==fath||ver[i]==hs[p]) continue;
dfs_(ver[i],p,0);
}
if(hs[p]) dfs_(hs[p],p,1);
cnt[dt[p]]++;
if(cnt[dt[p]]>cnt[tmpans]) tmpans=dt[p];
else if(cnt[dt[p]]==cnt[tmpans]&&dt[p]<tmpans) tmpans=dt[p];
for(ll i=head[p];i;i=nxt[i]) {
if(ver[i]==fath||ver[i]==hs[p]) continue;
getans(ver[i],p);
}
ans[p]=tmpans-dt[p];
if(!kp) clear(p,fath);
}
inline void addedge(ll u,ll v) {
ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {
do{buf[++len]=x%10+48;x/=10;}while(x);
}
else {
putchar('-');
do{buf[++len]=-(x%10)+48;x/=10;}while(x);
}
while(len>=0) putchar(buf[len--]);
}
inline void writeln(ll x) {
write(x);putchar('\n');
}
int main() {
n=read();
for(ll i=1;i<n;i++) {
u=read();v=read();
addedge(u,v);addedge(v,u);
}
dfs(1,0);dfs_(1,0,1);
for(ll i=1;i<=n;i++) {
writeln(ans[i]);
}
return 0;
}
|