安防 光速东莞网站建设,建站设计网站,做律师网站电销,淄博品牌策划公司1008 - H.HEX-A-GONE Trails
题目大意
有两个玩家和一棵树#xff0c;初始状态玩家一和玩家二分别在两个点 x , y x,\space y x, y#xff0c;每次操作可以走一个与当前点有连边并且双方都没走到过的点#xff0c;问最后是谁赢
解题思路
因为不能走走过的点#xff0c…1008 - H.HEX-A-GONE Trails
题目大意
有两个玩家和一棵树初始状态玩家一和玩家二分别在两个点 x , y x,\space y x, y每次操作可以走一个与当前点有连边并且双方都没走到过的点问最后是谁赢
解题思路
因为不能走走过的点因此每个人走的路径一定是一条链
很明显当玩家一不选择往与玩家二所在的点的路径走相当于把 x → y x\to y x→y 的链让给了玩家二
因此如果想要这么走就应该保证对方此时能走的链没有比你要走的长
那么可以开个数组存储 x → y x\to y x→y 路径上每个点只经过非路径上的点所能走的最长的链长可以用树形dp解决
这样操作之后就将问题转化到了数组中解决
双方分别用set维护在当前点所能到达的最远的距离
如果当前玩家离开 x → y x\to y x→y 的路径能到的最远的距离比对方set内的最大值大则必胜
如没有必胜策略则继续沿路径走并在双方set中删除不可达的方案
如果双方到见面了还没必胜则比较两者接下来能到的最远距离
具体细节参考代码哥们觉得太抽象了不好将
code
#include bits/stdc.h
using namespace std;
const int N 1e5 9;
struct lol {int x, y;} e[N 1];
int t, n, a, b, ans, top[N], vis[N], dep[2][N], f[2][N], p[N], fl;
multiset int s[2];
void ein(int x, int y) {e[ ans].x top[x];e[ans].y y;top[x] ans;
}
void dfs(int x, int fa, int op) {vis[x] ^ 1; f[op][x] fa; dep[op][x] dep[op][fa] 1;if ((x a || x b) fa ! 0) return;for (int i top[x]; i; i e[i].x) {int y e[i].y;if (y fa) continue;dfs(y, x, op);}
}
void dfs1(int x, int fa, int rt) {p[rt] max(p[rt], max(dep[0][x] - dep[0][rt], dep[1][x] - dep[1][rt]) 1);for (int i top[x]; i; i e[i].x) {int y e[i].y;if (vis[y] 2 || y fa) continue;dfs1(y, x, rt);}
}
int main() {scanf(%d, t);while (t --) {scanf(%d%d%d, n, a, b); ans fl 0;s[0].clear(); s[1].clear();for (int i 1; i n; i)top[i] p[i] vis[i] dep[0][i] dep[1][i] 0;for (int i 1, u, v; i n; i)scanf(%d%d, u, v), ein(u, v), ein(v, u);dfs(a, 0, 0);dfs(b, 0, 1);for (int x b; x; x f[0][x]) vis[x] 2;for (int x b; x; x f[0][x]) {dfs1(x, 0, x);if (x ! b) s[0].insert(p[x] dep[0][x] - 1);if (x ! a) s[1].insert(p[x] dep[1][x] - 1);}int x1 a, x2 b, i;for (i 0; x1 ! f[0][x2]; i)if ((i 1) 0) {if (p[x1] *prev(s[1].end()) - i / 2) {fl 1; break;}auto it s[0].find(p[x1] i / 2); s[0].erase(it);x1 f[1][x1];it s[1].find(p[x1] dep[1][x1] - 1); s[1].erase(it);} else {if (p[x2] *prev(s[0].end()) - (i 1) / 2) {fl 1; break;}auto it s[1].find(p[x2] i / 2); s[1].erase(it);x2 f[0][x2];it s[0].find(p[x2] dep[0][x2] - 1); s[0].erase(it);}if (fl) printf(%d\n, (i 1) ^ 1);else if ((i 1) 1) printf(%d\n, p[x2] p[x1] ? 0 : 1);else printf(%d\n, p[x1] p[x2] ? 1 : 0);}return 0;
}
