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 Iput	Standard Oputput
31 2 1 3 1 3	Yes
31 2 1 3 2 3	No

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