P相遇游戏
时间限制 : 20000 MS 空间限制 : - KB
评测说明 : 1s,256m
问题描述
何老板与郃德君在玩一款有趣的游戏，游戏虽然简单，他俩仍乐此不疲。
游戏在一个n个节点的地图上进行。游戏地图上有n-1条红色边，图中任意两点可通过红色边相互到达。地图上还有n-1条蓝色边，图中任意两点可通过蓝色边相互到达。
游戏开始时，何老板在x号点，郃德君在y号点。两人轮流操作。每一次操作，玩家可以移动到相邻的点，或者原地不动。何老板只能沿红色边移动，郃德君只能沿蓝色边移动。
如果某一刻，两人位于同一个节点(相遇)，游戏结束。如果游戏在第i次操作结束，游戏得分为i。何老板想使得游戏得分尽可能大，郃德君想使游戏得分尽可能小。
游戏双方都很聪明，输出最终的游戏得分。
解：
这是一道好题目
首先这题有两棵树 并且这是一个树上博弈题目 就很有意思
怎样推出老板的策略和合德的策略呢
我们注意到 老板的策略一定是朝着远离合德的方向都 而合德的策略一定是朝着靠近老ban的方向走
合德君追上老板的条件当且仅当 老板在走到一个点的最短距离sj>合德君走到的距离sj
所以在树上我们可以预处理距离根的最短距离
至于环的情况 很鬼畜...
首先必须满足何老板能够走到
然后还要满足这是一个鬼畜的环
至于判断的话 考虑枚举每条何老板的边 假如在hd兄的树上的距离>=3 则存在环
code：
//
#include<bits/stdc++.h>
using namespace std;
#define maxnn 410010
int dep1[maxnn],dep2[maxnn];
int las1[maxnn],en1[maxnn],nex1[maxnn],tot1;
int las2[maxnn],en2[maxnn],nex2[maxnn],tot2;
int las[maxnn],en[maxnn],nex[maxnn],tot=1;
int n,x,y;
int ans=0;
int f[maxnn][22];
int dis[maxnn];
struct node {
int st,en,le;
} ed[maxnn];
int cnt;
#define GC getchar()
inline int R() {
char t;
int f=1;
int x=0;
t=GC;
while(!isdigit(t)) {
if(t=='-') f=-1;
t=GC;
}
while(isdigit(t)) {
x=x*10+t-48;
t=GC;
}
return x*f;
}
void add1(int a,int b) {
en1[++tot1]=b;
nex1[tot1]=las1[a];
las1[a]=tot1;
}
void add2(int a,int b) {
en2[++tot2]=b;
nex2[tot2]=las2[a];
las2[a]=tot2;
}
int goup(int x,int s) {
int k=ceil(log2(n));
for(int i=0; i<=k; i++) {
if((s&(1<<i))) {
x=f[x][i];
}
}
return x;
}
int lca(int x,int y) {
if(dep2[x]<dep2[y])swap(x,y);
x=goup(x,dep2[x]-dep2[y]);
if(x==y) return y;
int s=ceil(log2(n));
for(int i=s; i>=0; i--) {
if(f[x][i]!=f[y][i]) {
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
void add(int a,int b) {
en[++tot]=b;
nex[tot]=las[a];
las[a]=tot;
}
void dfs1(int v,int fa) {
dep1[v]=dep1[fa]+1;
for(int i=las1[v]; i; i=nex1[i]) {
int u=en1[i];
if(u!=fa) {
dfs1(u,v);
}
}
}
void dfs2(int v,int fa) {
dep2[v]=dep2[fa]+1;
int s=log2(n);
f[v][0]=fa;
for(int i=1; i<=s; i++) {
f[v][i]=f[f[v][i-1]][i-1];
}
for(int i=las2[v]; i; i=nex2[i]) {
int u=en2[i];
if(u!=fa) {
dis[u]=dis[v]+1;
dfs2(u,v);
}
}
}
int vis[maxnn];
void ddfs(int v,int fa) {
if(dep1[v]>dep2[v]) return ;
vis[v]=1;
ans=max(ans,(dep2[v]-1)*2);
for(int i=las1[v]; i; i=nex1[i]) {
int u=en1[i];
if(u!=fa) {
ddfs(u,v);
}
}
}
int main() {
int xx,yy;
n=R();
x=R();
y=R();
for(int i=1; i<n; i++) {
xx=R();
yy=R();
add1(xx,yy);
add1(yy,xx);
ed[++cnt].st=xx;
ed[cnt].en=yy;
add(xx,yy);
add(yy,xx);
}
for(int i=1; i<n; i++) {
xx=R();
yy=R();
add2(xx,yy);
add2(yy,xx);
add(xx,yy);
add(yy,xx);
}
dfs1(x,0);
dfs2(y,0);
ddfs(x,0);
for(int i=1; i<n; i++) {
if((!vis[ed[i].en])&&(!vis[ed[i].st])) continue;
int dd=dis[ed[i].st]+dis[ed[i].en]-2*dis[lca(ed[i].en,ed[i].st)];
if(dd>=3) {
puts("-1");
return 0;
}
}
cout<<ans;
}