台州企业网站建设公司,群晖nas搭建wordpress,免费建设自己的网站,商务网站制作工程师problem
洛谷链接
solution
考虑一条 (u,v)(u,v)(u,v) 的红边#xff0c;在蓝树上 u,vu,vu,v 两点距离 ≥3\ge 3≥3。
如果先手到达 u,vu,vu,v 其中任何一点且下一步后手行动无法抓住先手#xff0c;那么这个游戏就将进入死循环了。
通过画图#xff0c;你会发现这个结…problem
洛谷链接
solution
考虑一条 (u,v)(u,v)(u,v) 的红边在蓝树上 u,vu,vu,v 两点距离 ≥3\ge 3≥3。
如果先手到达 u,vu,vu,v 其中任何一点且下一步后手行动无法抓住先手那么这个游戏就将进入死循环了。
通过画图你会发现这个结论是成立的后手一旦接近先手先手就立马到边的另一点再次拉远与后手的距离。钓系 这是我们判断 -1 的有利结论。将这些点打上标记
先手想要最大化游戏轮数换言之先手会想方设法地走一些红边到达标记点。
而这些可走边 (u,v)(u,v)(u,v) 自然而然均满足在蓝树上 u,vu,vu,v 的距离 ≤2\le 2≤2。
我们将蓝树以 yyy 为根提起来那么先手的起点 xxx 就在内部。
对于后手肯定是往先手所在的子树靠近而先手也是一定不可能跨过后手到其上方去。
最极端就是先手点在蓝树上是后手点儿子先手最多也只能往上跳两步然后变成后手父亲下一步就被抓。还不如一开始不往上跳。
所以先手是不可能跨过后手的一旦跨过下一步就被抓住。
基于此我们可以推出如果一个点 ppp 在红树上与 xxx 的距离 ≥\ge≥ ppp 在蓝树上与 yyy 的距离那么后手一定会在先手走到 ppp 的路上或 ppp 点将其抓住。
所以这种点先手绝对不可能走走就是去送死。那么唯一能走的就是在红树上与 xxx 的距离 在蓝树上与 yyy 的距离的点。
所以我们可以 dfs\text{dfs}dfs 通过可以走的边到达符合限制的点。
如果这些点中有被标记的那么就能进入无限循环。
否则最大答案一定是点在红树上与 xxx 的最大距离 ×2\times 2×2即到了站在原地等着抓。
code
#include bits/stdc.h
using namespace std;
#define maxn 200005
int n, x, y, ans;
vector int R[maxn], B[maxn];
pair int, int E[maxn];
int dis_b[maxn], dis_r[maxn], f[maxn];
bool vis[maxn];void dfs1( int u, int fa ) {f[u] fa;for( int v : B[u] ) if( v ^ fa ) {dis_b[v] dis_b[u] 1;dfs1( v, u );}
}bool check( int u, int v ) {if( dis_b[u] dis_b[v] ) swap( u, v );if( dis_b[u] dis_b[v] ) return f[u] ^ f[v];if( dis_b[u] dis_b[v] 1 ) return f[u] ^ v;if( dis_b[u] dis_b[v] 2 ) return f[f[u]] ^ v;return 1;
}void dfs2( int u, int fa ) {if( vis[u] ) { puts(-1); exit(0); }ans max( ans, dis_b[u] );for( int v : R[u] )if( v ^ fa ) {dis_r[v] dis_r[u] 1;if( dis_r[v] dis_b[v] ) dfs2( v, u );}
}int main() {scanf( %d %d %d, n, x, y );for( int i 1, u, v;i n;i ) {scanf( %d %d, u, v );R[u].push_back( v );R[v].push_back( u );E[i] make_pair( u, v );}for( int i 1, u, v;i n;i ) {scanf( %d %d, u, v );B[u].push_back( v );B[v].push_back( u );}dfs1( y, 0 );for( int i 1;i n;i ) {int u E[i].first, v E[i].second;if( check( u, v ) ) vis[u] vis[v] 1; //判断u,v是否是无限循环点}dfs2( x, 0 );printf( %d\n, ans 1 );return 0;
}
