这题的n有点大，1000000的数据规模只能考虑O(n)解决（貌似跟O(nlogn)的算法扯不上关系）。
先假定1为根，这样能把这个有根图转成一棵以1为根的树。再用f[i],son[i]表示在这棵树中，以i为根节点下面最大的深度之和（深度是相对于整棵树，而不是i来说的），以及i节点下有多少个子节点（包括自己）。可以使用一个简单的广搜确定父节点后，用一个简单的动规累加，完成这步需要O(2n)的时间。
之后我们考虑换根。对于根从当前根节点的fa换到它的某个最近孩子u上的情况：u和它的所有孩子的深度都会-1，u另外一边的节点的深度都会+1，因此换完根之后的深度和就是f[fa]-son[u]+(n-son[u])。将根从1到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
| /**************************************************************
Problem: 1131
User: abcdabcd987
Language: C++
Result: Accepted
Time:7432 ms
Memory:64740 kb
****************************************************************/
#include <iostream>
using namespace std;
struct link {
int v,next;
} g[3000000];
long long q[1000001],son[1000001],deep[1000001],father[1000001],f[1000001],n,top,ans,root;
bool s[1000001];
inline void join(const int x,const int y) {
g[++top].v=y;
g[top].next=g[x].next;
g[x].next=top;
}
void bfs(const int source) {
int head=0,tail=1;
q[tail]=source;
s[source]=true;
father[source]=-1;
deep[source]=1;
while (head<tail) {
int u=q[++head],v=g[u].next;
son[u]=1;
while (v!=-1) {
if (!s[g[v].v]) {
s[g[v].v]=true;
father[g[v].v]=u;
q[++tail]=g[v].v;
deep[tail]=deep[head]+1;
}
v=g[v].next;
}
}
for (int i=n;i>1;--i) {
f[q[i]]+=deep[q[i]];
son[father[q[i]]]+=son[q[i]];
f[father[q[i]]]+=f[q[i]];
}
}
int main() {
ios::sync_with_stdio(false);
cin>>n;
for (int i=1;i<=n;++i) g[i].next=-1;
top=n;
for (int i=1,x,y;i<n;++i) {
cin>>x>>y;
join(x,y);
join(y,x);
}
bfs(1);
ans=f[root=1];
for (int i=2;i<=n;++i) {
long long u=q[i],fa=father[u];
f[u]=f[fa]-son[u]+n-son[u];
if ((f[u]==ans&&u<root) || (f[u]>ans)) {
root=u;
ans=f[u];
}
}
cout<<root;
}
|
