第九场是真滴难,hdu多校很多场都是榜一前一小时内过6题左右，这场榜前三都是前一小时内只过了一题OAO
1001 Tree
如题名，先给了一颗树，然后这棵树看成是个有向图,方向为父亲指向儿子，每个点都有贡献，其贡献为这个点在图中能到达的点的个数
嗯，看起来贡献就是子树的大小siz[node]
然后，还给了你一条有向边，这条有向边的起点和终点是你自己选的，你要使所有点的贡献加起来最大，求最大的贡献是多少
分析：
做法:
枚举所有叶子节点为起点(枚举所有节点为起点也行),以根节点为终点的贡献
直接dfs一遍就行了
这题我们wa了几遍,原因是我没分析完就下结论了，我当时得出的结论是，选深度最大的点为起点，根节点为终点，然后wa了，之后我造了个1e5的一条链为数据，然后程序没跑出来，队友说是爆栈了，然后我就以为wa了是我用dfs爆栈了的原因，然后我观察到数据的输入有特殊要求,发现不用dfs也能做，然后又wa了，然后才发现是我分析的不够QAQ
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
const int MAXN = 5e5+7;
int deep[MAXN],son[MAXN],fa[MAXN];
long long su[MAXN];
bool bz[MAXN];
int main()
{
//freopen("cccc.out","r",stdin);
int T, n;
cin>>T;
while(T--){
scanf("%d",&n);
for(int i = 1;i <= n;i++) {
bz[i] = false;
son[i] = 0;
su[i] = 0;
}
fa[1] = 0;
deep[1] = 1;
int x;
for(int i = 2;i<=n;i++){
scanf("%d",&x);
fa[i] = x;
deep[i] = deep[x] + 1;
}
long long ans = 0;
for(int i = n;i;i--){
son[i]++;
son[fa[i]] += son[i];
ans += son[i];
}
long long ma = 0;
for(int i = 1;i<=n;i++){
su[i] = (long long)son[i] + su[fa[i]];
ma = max(ma,(long long)deep[i]*(long long)n-su[i]);
}
ans += ma;
printf("%lld\n",ans);
}
return 0;
}
1003待补
原文：https://www.cnblogs.com/ruanbaitql/p/13573338.html