杭电多校第九场 1001 Tree 题解

题目大意

给你一颗n个节点的树，树的序号为1~n，你可以在其中加入任意一条有向边，求树中任意两个可到达的节点的对数。

解题思路

我们可以发现，当某个节点x加条边到树的根节点的时候，是增加的最多的。

相当于把x节点与除了自己的子节点以外的节点都连了起来。

增加的数量为$n-num[x]$。

其中$num[i]$为i节点的子节点数量。

当你加入了这条边之后，同时他的父节点都会受到影响。

所以增加的数量为$n-num[x]+f[fa]$。

$f[i]$为加入i到根节点的边新增的对数。

取其中的最大值，在加上所有节点的子节点数量，就是最终答案。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 5e5 + 5;
vector<int> v[N];
ll f[N], ans, sum, num[N];
int n;

void dfs(int x) {
	num[x] = 1;
	for (auto t : v[x]) {
		dfs(t), num[x] += num[t];
	}
}

void Dfs(int x,int fa) {
	sum += num[x];
	f[x] = 1LL * n - num[x] + f[fa];
	ans = max(ans, f[x]);
	for (auto t : v[x]) {
		Dfs(t, x);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin>>t;
	while (t--) {
		cin >> n;
		for (int i = 1; i <= n; i++)	v[i].clear(), f[i] = 0;
		for (int i = 2; i <= n; i++) {
			int x; cin >> x; v[x].push_back(i);
		}
		dfs(1);
		ans = sum = 0;
		Dfs(1, 0);
		cout << ans + sum << endl;
	}
	return 0;
}