P6584
题目描述
小 Z 和 \(m\) 个 Youyou 在一棵树上相遇了！
这棵树上，每条边的长度都是 \(1\)。
初始时，小 Z 在 \(x\) 号节点上，并且有一把射程为 \(k\) 的枪。
因为小 Z 技术精湛，所以 Youyou 一打就死，而小 Z 永远不会死掉。
小 Z 和 Youyou 都按回合行动，在每一回合中，按照下面的顺序行动：
-
回合计数器 \(+1\)（初始为 \(0\)）。
-
小 Z 可以用枪射死与小 Z 树上距离小于等于 \(k\) 的所有 Youyou。
-
如果所有 Youyou 都被消灭了，游戏结束，这时回合计数器的值就是小 Z 用的回合数。
-
小 Z 可以选择沿着一条边，移动到任意相邻节点，也可以选择不动。
-
所有 Youyou 都会沿着他和小 Z 的简单路径向小 Z 移动一条边的距离。如果此时他们在同一个节点，则不动。
小 Z 需要求出消灭所有敌人需要的最小回合数。
题解
我们考虑所有操作中特殊的：小 Z 可以选择沿着一条边，移动到任意相邻节点，也可以选择不动。我们发现，动不一定优，简单难说，当小 Z 朝一个 Youyou 走时，其他子树的 Youyou 与小 Z 相对不变，这样，当小 Z 打完那个 Youyou 时，还要调头打其余的 Youyou 。
于是，我们有了一个思路：
1.打击其他子树的 Youyou。
2.向最深的 Youyou前进。
我们预处理出 \(dp[i]\) 表示在以 \(i\) 为根节点得到子树中，最远 \(Youyou\) 与 \(i\) 的距离。模拟上述两个操作即可，值得注意的是，题中操作顺序繁琐，细节颇多。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+100;
int k,n,m,root,dp[N];
bool f[N];
vector<int>edge[N];
void dfs1(int x,int fa)
{
if(f[x]==1)
dp[x]=0;
for(int i=0;i<edge[x].size();i++)
{
int to=edge[x][i];
if(to==fa)
continue;
dfs1(to,x);
dp[x]=max(dp[x],dp[to]+1);
}
return;
}
void dfs2(int x,int fa,int nw)
{
int mx=-1,mn=-1,mxd,mnd;
for(int i=0;i<edge[x].size();i++)
{
int to=edge[x][i];
if(to==fa)
continue;
if(dp[to]>mx)
{
mn=mx;
mnd=mxd;
mx=dp[to];
mxd=to;
}
else if(dp[to]>mn)
{
mn=dp[to];
mnd=to;
}
}
mx++,mn++;
int us=max(mn-nw-k,0);
if(mx-us-nw<=k)
{
cout<<nw+us+1;
exit(0);
}
dfs2(mxd,x,nw+us+1);
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
}
cin>>m;
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
f[x]=1;
}
cin>>k>>root;
memset(dp,-63,sizeof(dp));
dfs1(root,0);
dfs2(root,0,0);
return 0;
}