思维好题+技巧好题 *1900
Cirno_9baka 有一棵包含 n 个节点的树。他愿意把它与你分享，这意味着你可以对它进行一些操作。
最初，树的 1 号节点上有两个棋子。对每个操作，您可以选择任意一个棋子，并将其移动到相邻节点。你需要确保两个棋子之间的距离不会超过 d。
给你两个序列，分别表示两个棋子需要经过的节点（可以以任何顺序经过）。最终，它们必须回到根节点。作为一个好奇的男孩，Cirno_9baka 想知道最少操作次数。
先考虑对1棋子进行移动：
若1棋子点要去往 p 节点，那么显然1到p这条链上的所有节点都要经过
接下来是本题的精髓地方: 我们考虑只点不考虑边，倘若一个点要走，那么它对答案的贡献是2，来一次回一次
考虑从1棋子从1号节点开始，如何最少步骤的走完m个目标点？
有一个显然的贪心，记录所有走过的点，步骤就是 （点的数量-1）*2
比如我们现在要前往6，5
路径便是 1→2→3→4→6→4→3→5→3→2→1
显然最优解就是每条边走两边，对应到点就是(所有走过的点-1)*2，因为1号节点不算
对2棋子也是同理，这样我们可以统计好所有要走的点
现在加入题目条件:你需要确保两个棋子之间的距离不会超过 d
仔细想想如何1棋子去了足够深的点，那么2棋子一定要去这个点的第d祖先点
但到这里我们不好算出一个点的第d祖先点，就算算出这个祖先点也不好统计答案
那么接下来就是本题很有技巧的地方了
如何判断一个点对于1棋子和2棋子该不该走
（对于1棋子走，2棋子同理）该走的条件：1.这是1棋子的目标点之一 2.这是1棋子从1号根节点到目标节点路径上的一点 3.这个节点的子树里有2棋子的目标节点，且他们两的距离差大于d，当然出于贪心，我们要选最深的那个目标节点(如果他们距离小于等于d，这节点显然不用走)
这其中3条件是最难的想也是最难理解的，那么如何判断3条件呢？
这里我们用一个很炫的技巧:dp1[x]表示 以x子树包括x，1棋子去往最深的目标点。dp2[x]表示 以x子树包括x，2棋子去往最深的目标点
这时候我们就很好判断了
比如对于1号棋子:如果dp1[x]有值,那么1号棋子一定会去往x这个点
如果dp2[x]-dep[x]>=d那么x也是一定要去（对应3条件，真的很妙）
当然还要注意的是，1号节点是不用管的
if(x==1) return; if(dp1[x]||dp2[x]-dep[x]>=d) ans+=2; if(dp2[x]||dp1[x]-dep[x]>=d) ans+=2;
Code：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back //vector函数
#define popb pop_back //vector函数
#define fi first
#define se second
const int N=2E5+10;
//const int M=;
//const int inf=0x3f3f3f3f; //一般为int赋最大值,不用于memset中
//const ll INF=0x3ffffffffffff; //一般为ll赋最大值,不用于memset中
int T,n,ans=0,d,dep[N],dp1[N],dp2[N];
bool vis1[N],vis2[N];
vector<int> g[N];
inline int read()
{
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<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void dfs(int x,int fa)
{
dep[x]=dep[fa]+1;
if(vis1[x]) dp1[x]=dep[x];
if(vis2[x]) dp2[x]=dep[x];
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==fa) continue;
dfs(v,x);
dp1[x]=max(dp1[x],dp1[v]);
dp2[x]=max(dp2[x],dp2[v]);
}
if(x==1) return;
if(dp1[x]||dp2[x]-dep[x]>=d) ans+=2;
if(dp2[x]||dp1[x]-dep[x]>=d) ans+=2;
}
int main()
{
// freopen("","r",stdin);
// freopen("","w",stdout);
n=read();d=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
g[u].pb(v);g[v].pb(u);
}
int m=read();
for(int i=1;i<=m;i++) { int x=read();vis1[x]=1; }
m=read();
for(int i=1;i<=m;i++) { int x=read();vis2[x]=1; }
dfs(1,0);
printf("%d\n",ans);
return 0;
}
思维+技巧题可真TM的难
标签：ch,dp2,dp1,CF1774E,int,棋子,节点 From： https://www.cnblogs.com/Willette/p/17045241.html