大概是树dp最后一发
题意要求每个点做根的时候中最大值
我们显然不能直接舍掉点不考虑
所以考虑点与点之间的dp[]的转移
转移也就是父子之间转移
我们发现根节点上移一位的时候 子树所有点权值++ 其它权值--
所以开一个dp[]
Time cost: 65min
Code:
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<cmath>
5 #include<queue>
6 #include<iostream>
7 #define ms(a,b) memset(a,b,sizeof a)
8 #define rep(i,a,n) for(int i = a;i <= n;i++)
9 #define per(i,n,a) for(int i = n;i >= a;i--)
10 #define inf 2147483647
11 using namespace std;
12 typedef long long ll;
13 typedef double D;
14 #define eps 1e-8
15 ll read() {
16 ll as = 0,fu = 1;
17 char c = getchar();
18 while(c < '0' || c > '9') {
19 if(c == '-') fu = -1;
20 c = getchar();
21 }
22 while(c >= '0' && c <= '9') {
23 as = as * 10 + c - '0';
24 c = getchar();
25 }
26 return as * fu;
27 }
28 //head
29 const int N = 1000003;
30 int n;
31
32 int head[N],nxt[N<<1],mo[N<<1],cnt;
33 void _add(int x,int y) {
34 mo[++cnt] = y;
35 nxt[cnt] = head[x];
36 head[x] = cnt;
37 }
38 void add(int x,int y) {if(x^y)_add(x,y),_add(y,x);}
39
40 ll dp[N];
41 int sze[N];
42 void dfsdwn(int x,int f) {
43 sze[x] = 1;
44 for(int i = head[x];i;i = nxt[i]) {
45 int sn = mo[i];
46 if(sn == f) continue;
47 dfsdwn(sn,x);
48 sze[x] += sze[sn];
49 }
50 }
51
52 void dfsup(int x,int f) {
53 // if(x ^ f) up[x] = up[f] + dn[f] - dn[x] + n - (sze[x]<<1);
54 for(int i = head[x];i;i = nxt[i]) {
55 int sn = mo[i];
56 if(sn == f) continue;
57 dp[sn] = dp[x] + n - (sze[sn]<<1);
58 dfsup(sn,x);
59 }
60 }
61
62 int main() {
63 n = read();
64 rep(i,2,n) add(read(),read());
65 dfsdwn(1,1),dfsup(1,1);
66 dp[0] = -1;
67 int maxid = 0;
68 rep(i,1,n) if(dp[maxid] < dp[i]) maxid = i;
69 printf("%d
",maxid);
70 return 0;
71 }