Edge Game 最短路

Input file: standard Input file: standard Input Output file: standard Output Time limit: 1 second Memory limit: 512 megabytes

Problem Description

Cuber QQ know an Edge Game, in which two players move their tokens on edges alternatively. Specifically, the game starts with a fixed and given undirected tree. Player A and Player B each has a token on one node. They move in turn. In each step, the player moves his/her own token to a node adjacent to the current node located. Player A moves first. The player who first moves his/her token on the other’s wins. Determine if A can win if each plays optimally.

Input

In the first line there is one integer n (1 ≤ n ≤ 105 ), representing the number of nodes in the tree.

In each of the next n − 1 lines are two integers u, v (1 ≤ u, v ≤ n, u 6= v) each, representing there is an edge between node u and node v.

In the last line are two integers a, b (1 ≤ a, b ≤ n, a 6= b), representing the node A’s token and B’s token is on initially.

Output

One line “Yes” or “No”, denoting the winner.

Example

Standard IputStandard Oputput31 21 31 3Yes31 21 32 3No

Solution

😀 算法标签：最短路/LCA 规律

容易想到的一个思路是：找到两点间的最短路，然后判断最短路的奇偶性。奇数则赢，偶数则负。

最短路可以跑 D i j s t r a Dijstra Dijstra，也可以 S P F A SPFA SPFA，但是需要堆优化( p r i o r i t y _ q u e u e priority\_queue priority_queue)，直接 C o p y Copy Copy标准模板修改一下即可。

需要注意的是：1.建双向边 2.边权置1

#include 
#define itn int
#define ll long long
#define rnt register int
#define ull unsigned long long
#define IOF ios_base::sync_with_stdio(false)
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int dis[N];
bool via[N]; 
int n, m, a, b;
struct node {
    int to, dis;
    node(int tt = 0, int dd = 0) : to(tt), dis(dd) {}
    friend bool operator n2.dis; }
};
vector vec[N];
priority_queue q; 
int dijstra(int start, int end){
    memset(via, false, sizeof(via));
    dis[start] = 0;
    q.push(node(start, 0));
    while (!q.empty()){
        node now = q.top();
        q.pop();
        if (!via[now.to]){
            via[now.to] = true;
            for (int i = 0; i  n;
    for (int i = 1; i  u >> v;
        vec[u].push_back(node(v, 1));
        vec[v].push_back(node(u,1));
    }
    cin >> a >> b;
    if(dijstra(a, b) % 2 == 0) cout