General idea of the topic

Given a tree with \ (n(1\leq n\leq 2\times 10^5) \) points, some edges of the tree have edge weight and some edges have no edge weight. Given \ (m(1\leq m\leq 2\times 10^5) \) restrictions, whether the number of \ (1 \) bits on the exclusive or sum of edge weights on the path from \ (u \) to \ (v \) is odd or even. Now it is required to give edge weight to the edge without edge weight, so that all restrictions are met.

Problem solution

Let \ (f(x) \) represent the parity of the number of \ (1 \) on the binary bit of \ (x \), that is, if there are even \ (1 \) on the binary bit of \ (x \), then \ (f(x)=0 \); If there are an odd number of \ (1 \) on the binary bit of \ (x \), then \ (f(x)=1 \). Assuming that there are a series of edge weights \ (\ {w_1,w_2,\cdots,w_k \} \) on the path from \ (u \) to \ (v \), each time \ (f (w_1 \ bigopus w_2 \ bigopus \ cdots \ bigopus w_k) = 0 \) or \ (f (w_1 \ bigopus w_2 \ bigopus \ cdots \ bigopus w_k) = 1 \) is limited. Obviously, there is \ (f (w_1 \ bigopus w_2 \ bigopus \ cdots \ bigopus w_k) = f (w_1) \ bigopus f (w_2) \ bigopus \ cdots \ bigopus f (w_k) \), so we can regard the original edge weight \ (w \) as \ (f(w) \), and the edge weight to be given is either \ (0 \) or \ (1 \).

Let \ (s[u] \) represent the exclusive or sum of \ (f(w) \) on the path from \ (U \) to the root, then \ (s[u] \ bigopus [v] = 0 \) or \ (s[u] \ bigopus [v] = 1 \) are limited each time. For the edge \ ((u,v,w) \) with existing edge weight, it is equivalent to limiting \ (s[u] \ bigopus [v] = f(w) \). Therefore, we can create a new graph for all these restrictions. When the value of \ (s[u] \ bigopus [v] \) is limited, an edge is directly connected between \ (u,v \), and the edge weight is \ (s[u] \ bigopus [v] \). At this time, the exclusive or of the point weights \ (s[u],s[v] \) of \ (u,v \) should be equal to the edge weight. In the new graph, several connected blocks can be divided. In each connected block, only when the point weight \ (s[u] \) of a point \ (U \) is equal to \ (0 \) or \ (1 \) at the beginning, all the point weights in the connected block have been determined and can be obtained through XOR edge weight transfer. If there is a contradiction whether the point weight is assigned to \ (0 \) or \ (1 \), there is no solution. So we calculate the \ (s[u] \) of a combination method. Finally, for the edge \ ((fa,u) \) without edge weight at the beginning, if \ (FA \) is the father of \ (U \), the edge weight of \ ((fa,u) \) can be assigned as \ (s[u] \ bigopolus [fa] \).

Time complexity \ (O(n+m) \).

Code

#include <bits/stdc++.h>
using namespace std;

template<typename elemType>
inline void Read(elemType& T) {
    elemType X = 0, w = 0; char ch = 0;
    while (!isdigit(ch)) { w |= ch == '-';ch = getchar(); }
    while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    T = (w ? -X : X);
}

struct Graph {
    struct edge { int Next, to, w; };
    edge G[800010];
    int head[200010];
    int cnt;

    Graph() :cnt(2) {}
    void clear(int n) {
        cnt = 2;fill(head, head + n + 2, 0);
    }
    void add_edge(int u, int v, int w) {
        G[cnt].w = w;
        G[cnt].to = v;
        G[cnt].Next = head[u];
        head[u] = cnt++;
    }
};
Graph G, G2;
bool vis[200010];
int s[200010];
int T, n, m;

inline int f(int x) { return __builtin_parity(x); }

void Output(int u, int fa) {
    for (int i = G.head[u];i;i = G.G[i].Next) {
        int v = G.G[i].to;
        if (v == fa) continue;
        if (G.G[i].w == -1) printf("%d %d %d\n", u, v, s[u] ^ s[v]);
        else printf("%d %d %d\n", u, v, G.G[i].w);
        Output(v, u);
    }
}

vector<int> buf;

bool DFS(int u) {
    vis[u] = true;
    buf.push_back(u);
    for (int i = G2.head[u];i;i = G2.G[i].Next) {
        int v = G2.G[i].to, w = G2.G[i].w;
        if (vis[v]) {
            if (s[v] ^ s[u] != w) return false;
            continue;
        }
        s[v] = w ^ s[u];
        if (!DFS(v)) return false;
    }
    return true;
}

int main() {
    Read(T);
    while (T--) {
        Read(n);Read(m);
        G.clear(n);
        G2.clear(n);
        for (int i = 1;i <= n - 1;++i) {
            int u, v, w;
            Read(u); Read(v); Read(w);
            G.add_edge(u, v, w);
            G.add_edge(v, u, w);
            if (w != -1) {
                w = f(w);
                G2.add_edge(u, v, w);
                G2.add_edge(v, u, w);
            }
        }
        fill(vis + 1, vis + n + 1, false);
        bool flag = true;
        for (int i = 1;i <= m;++i) {
            int u, v, w;
            Read(u); Read(v); Read(w);
            if (u == v) {
                if (w) flag = false;
                continue;
            }
            G2.add_edge(u, v, w);
            G2.add_edge(v, u, w);
        }
        if (!flag) { printf("NO\n"); continue; }
        for (int u = 1;u <= n;++u) {
            if (vis[u]) continue;
            s[u] = 0; buf.clear();
            if (!DFS(u)) {
                for (auto x : buf) vis[x] = false;
                buf.clear(); s[u] = 1;
                if (!DFS(u)) { flag = false; break; }
            }
        }
        if (!flag) {
            printf("NO\n");
            continue;
        }
        printf("YES\n");
        Output(1, 0);
    }
    return 0;
};