题解 P7320 【[JSOI2013] 哈利波特与死亡圣器】
lzqy_
·
·
题解
分析
先考虑当 i 号节点被攻克时，哪些节点需要修筑好防御。
按照题意，由于下一步伏地魔大军可能前往任何它的子节点，所以，它所有的子节点都要修筑好防御。
然后分析当 i 号节点被攻克时，哪些节点已经修筑好防御。
伏地魔要攻克到 i 节点，需要走 (1,i) 的路径，攻克这一路上所有的节点。按照上面的结论可得：
那么对于 $i$ 节点，对这么多节点修筑好防御有多少时间呢？
不难发现，如果设 $1$ 号节点的深度为 $1$，那么把这些节点修筑好防御的时间恰好是节点 $i$ 的深度。
也就是说，需要找到一个整数 $ans$，使得 $\forall i\leq n$，都满足以上结论。
## 代码
具体实现看代码，有详细注释：
```cpp
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n,ans,x,y;
vector<int>v[300001];
void dfs(int fa,int x,int sum,int step)
{//fa:当前节点的父节点 x:当前节点
//sum:目前节点被攻克时，需要修筑好防御的节点数 step:当前节点深度
sum+=v[x].size()-1;//加上目前节点的子节点
if(x==1) sum++;
//如果是根节点，那么所有连边连到的点全部都是子节点，额外加一
ans=max(ans,(int)ceil(sum*1.0/step));
//计算在step小时内修筑sum个节点需要的人数，刷新最大值
for(register int i=v[x].size()-1; i>=0; i--)
if(v[x][i]!=fa)
dfs(x,v[x][i],sum,step+1);
}
int main()
{
cin>>n;
for(register int i=1; i<n; i++)
cin>>x>>y,v[x].pb(y),v[y].pb(x);
dfs(0,1,0,1);
cout<<ans<<endl;
return 0;
}
```
### 祝大家AC愉快！