HDU 5963 朋友

题目大意

B君在围观一群男生和一群女生玩游戏，具体来说游戏是这样的：

给出一棵n个节点的树，这棵树的每条边有一个权值，这个权值只可能是0或1。在一局游戏开始时，会确定一个节点作为根。接下来从女生开始，双方轮流进行操作。

当一方操作时，他们需要先选择一个不为根的点，满足该点到其父亲的边权为1; 然后找出这个点到根节点的简单路径，将路径上所有边的权值翻转（即0变成1，1 变成0 )。

当一方无法操作时(即所有边的边权均为0)，另一方就获得了胜利。

如果在双方均采用最优策略的情况下，女生会获胜，则输出“Girls win!”，否则输出“Boys win!”。

为了让游戏更有趣味性，在每局之间可能会有修改边权的操作，而且每局游戏指定的根节点也可能是不同的。

具体来说，修改边权和进行游戏的操作一共有m个，具体如下：

∙“0 x”表示询问对于当前的树，如果以x为根节点开始游戏，哪方会获得胜利。

∙“1 x y z ”表示将x和y之间的边的边权修改为z。

B君当然知道怎么做啦！但是他想考考你。

Input

包含至多5组测试数据。

第一行有一个正整数，表示数据的组数。

接下来每组数据第一行，有二个空格隔开的正整数n,m，分别表示点的个数，操作个数。保证n,m< 40000。

接下来n-1行，每行三个整数x,y,z，表示树的一条边。保证\(1<x<n, 1<y< n, 0 <= z <= 1\)

接下来m行，每行一个操作，含义如前所述。保证一定只会出现前文中提到的两种格式。

对于操作0，保证1 <= x <= n ;对于操作1，保证1 <= x <= n, 1 <= y <= n, 0 <= z <= 1，保证树上存在一条边连接x和y。

Output

对于每组数据的每一个询问操作，输出一行“Boys win!”或者“Girls win!”

Solusion

通过模拟样例有点感觉

回到根节点至少需要两次通过同一路径

那么很显然这个题的突破口就在判断“能不能走两次”的问题上

那么就去判断奇偶性

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

inline int read(){

    int x = 0, w = 1;

    char ch = getchar();

    for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;

    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';

    return x * w;

}

const int maxn = 55505;

struct node{

    int to, nxt, w;

}edge[maxn << 1];

int head[maxn], tot;

int ans[maxn];

inline void add(int x, int y, int z){

    edge[++tot].to = y;

    edge[tot].nxt = head[x];

    edge[tot].w = z;

    head[x] = tot;

}

int main(){

    // freopen("1.out", "w", stdout);

    int T = read();

    // cout << T << endl;

    while(T--){

        tot = 1;

        memset(head, 0, sizeof head);

        memset(ans ,0, sizeof ans);

        int n = read(), m = read();

        for(int i = 1; i <= n - 1; i++){

            int u = read(), v = read(), w = read();

            add(u, v, w);

            add(v, u, w);

            ans[u] += w;

            ans[v] += w;

        }

        while(m--){

            int op = read();

            if(op == 1){

                int u = read(), v = read(), w = read();

                int k;

                for(int i = head[u]; i; i = edge[i].nxt){

                    if(edge[i].to == v){

                        k = i;

                        break;

                    }

                }

                if(edge[k].w != w){

                    edge[k].w = w;

                    if(w) ans[u] += 1, ans[v] += 1;

                    else ans[u] -= 1, ans[v] -= 1;

                    edge[k ^ 1].w = w;

                }

            }

            else {

                int u = read();

                if(ans[u] % 2) cout << "Girls win!\n";

                else cout << "Boys win!\n";

            }

        }

    }

    return 0;

}

巴特西

HDU 5963 朋友（找规律，思维）

HDU 5963 朋友

题目大意

Input

Output

Solusion

最新文章

热门文章

巴特西

HDU 5963 朋友 （找规律，思维）

HDU 5963 朋友

题目大意

Input

Output

Solusion

最新文章

热门文章

HDU 5963 朋友（找规律，思维）