[??记录]AT2063 [AGC005E] Sugigma: The Showdown

**题意** : 给出两颗标号对应的树 $T_1,T_2$。 $A,B$ 两人进行游戏，初始时， $A$ 在点 $u$ ，$B$ 在点 $v$。 两人轮流操作，$A$ 为先手。 $A$ 可以利用 $T_1$ 中的边移动（或不移动）， $B$ 可以利用 $T_2$ 中的边移动（或不移动）。 当两人相遇时游戏结束， $A$ 想最大化游戏轮数， $B$ 想最小化游戏轮数，问游戏会进行多少轮。（可能为无限轮） $n\leq 2\times 10^5$ ，时限$\texttt{2s}$。 ------------ 考虑何时游戏会进行无限轮。 若 $T_1$ 中相邻的两个点在 $T_2$ 中距离 $\geq 3$ ，则 $A$ 只需要在两个点反复横跳，即可永远不被抓到。 假设 $T_1$ 中相邻的两个点在 $T_2$ 中距离总是 $\leq 2$ ，以 $B$ 所在的点为根，我们发现，$A$ 不可能走出 $T_2$ 中自己所在的子树。 因为 $A$ 若要跨越 $B$ ，则和 $B$ 距离必然为 $1$ ，下一步就会被吃掉。原地等待也是下一步被吃掉，不会更劣。 于是， $B$ 的最优决策一定是每次向着 $T_2$ 中 $A$ 所在的子树行走。 记 $dis_1[t]$ 表示 $T_1$ 上 $u,t$ 的距离， $dis_2[t]$ 表示 $T_2$ 上 $v,t$ 的距离。 若点 $t$ 满足 $dis_1[t]\geq dis_2[t]$ ，那么 $A$ 就不能前往该点。 在 $T_1$ 上搜索，求出 $A$ 能前往的点的集合，判定是否能进行无限轮，若不行，则前往 $dis_2[t]$ 最大的点并等待，答案为 $2dis_2[t]$。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #define pb push_back #define MaxN 200500 using namespace std; vector<int> g0[MaxN],g1[MaxN]; int dis0[MaxN],dis1[MaxN]; void pfs0(int u,int fa) { for (int i=0;i<g0[u].size();i++) if (g0[u][i]!=fa){ dis0[g0[u][i]]=dis0[u]+1; pfs0(g0[u][i],u); } } int f[MaxN]; void pfs1(int u,int fa) { f[u]=fa; for (int i=0;i<g1[u].size();i++) if (g1[u][i]!=fa){ dis1[g1[u][i]]=dis1[u]+1; pfs1(g1[u][i],u); } } bool chk(int u,int v) {return !(f[u]==v||f[v]==u||f[u]==f[v]||f[f[u]]==v||f[f[v]]==u);} bool fl[MaxN];int ans; void dfs(int u,int fa) { if (dis0[u]>=dis1[u])return ; if (fl[u]){puts("-1");exit(0);} ans=max(ans,2*dis1[u]); for (int i=0;i<g0[u].size();i++) if (g0[u][i]!=fa) dfs(g0[u][i],u); } int n,s0,s1; int main() { scanf("%d%d%d",&n,&s0,&s1); for (int i=1,u,v;i<n;i++){ scanf("%d%d",&u,&v); g0[u].pb(v);g0[v].pb(u); }pfs0(s0,0); for (int i=1,u,v;i<n;i++){ scanf("%d%d",&u,&v); g1[u].pb(v);g1[v].pb(u); }pfs1(s1,0); for (int u=1;u<=n;u++) for (int i=0;i<g0[u].size();i++) if (chk(u,g0[u][i])) fl[u]=fl[g0[u][i]]=1; dfs(s0,0); printf("%d",ans); return 0; } ```