【HDU6867】Tree 2020多校赛9（树形DP，贪心，爆搜）

problem

Tree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 126 Accepted Submission(s): 65

Problem Description
You are given a tree consisting of n vertices numbered 1 to n rooted at node 1. The parent of the i-th vertices is pi. You can move from a vertex to any of its children. What’s more, you can add one directed edge between any two different vertices, and you can move through this edge too. You need to maximize the number of pairs (x,y) such that x can move to y through the edges after adding the edge. Note that x can also move to x.

Input
The first line contains one integer T (1≤T≤100000) — the number of test cases.

The first line of each test case contains only one integer n(1≤n≤5×105) — the number of vertices in the tree.

The second line of each test case contains n−1 integers p2,p3,…,pn(1≤pi<i) — the parent of each non-root node.

The sum of n over all test cases does not exceed 106.

Output
Print T integers — for each test case output the maximum number of pairs (x,y) that vertices x can move to y after adding one edge.

Sample Input
2
5
1 1 2 2
6
1 2 3 1 3

Sample Output
17
26

Source
2020 Multi-University Training Contest 9

Recommend
IceyWang | We have carefully selected several similar problems for you: 6876 6875 6874 6873 6872

• 2020 Multi-University Training Contest 9
• 给定一棵树，随意连一条边构成基环树
• 求怎样构造使得相互连通的点对数量最大

solution

调了一下午TLE，最后发现被vector卡常数，可还行。。。

• 要让可以相互连通的点最大化，其实就是把叶节点和根节点连起来（贪心）
• 把任意叶节点和根节点连起来后，会形成一个环（基环外向树），然后环上的每个点都能拥有n条边
• 所以对于每个在环上的点，整体可以增加n-leaves[i]条路，其中leave[i]表示有向图中每个点的子节点个数。
• 所以连通点数最多的路线其实就是cnt+n-leaves[i]最大的那个环，即O(1)统计当前点为环上点时相互连通的点对数。

1、先dfs一遍预处理出每个点子节点个数leaves[i]
2、再dfs一次，每次比较，连接当前点和1之后，相互连通的数量，取最大值。
3、注意vector和cin会TLE
4、注意const int maxn会MLE

用简单的树形dp来理解：我们加的边⼀一定是从叶⼦子到根（贪心），即枚举（爆搜）每个叶子和根连边，然后结论O(1)统计互相连通的个数，状态转移取最大值即可。

对于环的大小，因为都是和根连接，所以直接就是当前叶子节点的深度。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
const int maxn = 50050;
typedef long long LL;

//vector<int>G[maxn];
int tot, v[1000005],nxt[1000005],h[1000005];
int leaves[1000005], n;
LL ans;
void addedge(int x,int y){v[++tot]=y; nxt[tot]=h[x]; h[x]=tot;}
int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void init(int x){
	/*
    for(int i = 0; i < G[x].size(); i++){
        int y = G[x][i];
        init(y);
        leaves[x] += leaves[y];
    }
	*/
	for(int p = h[x]; p;p=nxt[p]){
		init(v[p]);
		leaves[x] += leaves[v[p]];
	}
}
void dfs(int x, LL cnt){
    ans = max(ans, cnt);
	/*
    for(int i = 0; i < G[x].size(); i++){
        int y = G[x][i];
        dfs(y,cnt+n-leaves[y]);
    }
	*/
	for(int p=h[x];p;p=nxt[p]){
		dfs(v[p],cnt+n-leaves[v[p]]);
	}
}

int main(){
    int T = readint();
    while(T--){
        n = readint();
        for(int i = 1; i <= n; i++){
            leaves[i] = 1;
            //G[i].clear();
			h[i] = 0; tot = 0;
            ans = 0;
        }
        for(int i = 2; i <= n; i++){
            int x = readint();
            //G[x].push_back(i);
			addedge(x,i);
        }
        init(1);
        dfs(1,0);
        for(int i = 1; i <= n; i++)
            ans += leaves[i];
        printf("%lld\n",ans);
    }
    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
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/108086233