ABC126-D: Even Relation 供養

Dに一時間以上費やすも解けず蒸発
とりあえずめっちゃ書いたので供養
ACコードではない

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

long long const N = 100010;

long long n;
struct edge {
    long long cost, to;
};
vector<edge> G[N];

vector<bool> F(N); // true: even
vector<bool> Check(N);

void dfs(long long now, bool fst, int od){ // syokai?, odd?
    Check[now] = true;
    if(fst){
        for(long long i = 0; i < G[now].size(); i++){
            
        }
    }else
        for(long long i = 0; i < G[now].size(); i++){

        }
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n;
    for(long long i = 0; i < n - 1; i++){
        long long u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        G[u].push_back({w, v});
        G[v].push_back({w, u});
    }

    for(long long i = 0; i < n; i++){
        if(Check[i]) continue;
        dfs(i, true, -1);
    }

    return 0;
}

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

long long const N = 100010;

long long n;
struct edge {
    long long cost, to;
};
vector<edge> G[N];

vector<bool> BF(N);
vector<bool> Check(N);

struct UnionFind{
    vector<long long> par;
    UnionFind(int NN) : par(NN){
        for(long long i = 0; i < NN; i++){
            par[i] = -1;
        }
    }
    long long root(int x){
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    void unite(long long x, long long y){
        long long rx = root(x);
        long long ry = root(y);
        if(rx == ry) return;
        else{
            if(par[rx] > par[ry]) swap(rx, ry);
            par[rx] += par[ry];
            par[ry] = rx;
       }
    }
    bool same(int x, int y){
        return root(x) == root(y);
    }
    void check(){
        for(auto x : par){
            cout << x << " ";
        }
        cout << endl;
    }
};

void dfs_first(long long now){
    // BF[now] = true;
    Check[now] = true;
    long long gs = 0; // gusu_count
    for(long long i = 0; i < G[now].size(); i++){
        edge e = G[now][i];
        if(e.cost % 2 == 0) gs++;
    }
    if(gs * 2 == (long long)G[now].size()){
        for(long long i = 0; i < G[now].size(); i++){
            edge e = G[now][i];
            BF[e.to] = false;
            Check[e.to] = true;
        }
    }else{
        if(gs > (long long)G[now].size() / 2){
            BF[now] = true;
            for(long long i = 0; i < G[now].size(); i++){
                edge e = G[now][i];
                if(e.cost % 2 == 0){
                    BF[e.to] = true;
                }else{
                    BF[e.to] = false;
                }
                Check[e.to] = true;
            }
        }else{
            BF[now] = false;
            for(long long i = 0; i < G[now].size(); i++){
                edge e = G[now][i];
                if(e.cost % 2 == 0){
                    BF[e.to] = true;
                }else{
                    BF[e.to] = false;
                }
                Check[e.to] = true;
            }
        }
    }
}

void dfs_second(long long now){
    long long bc = 0; // brack_count
    long long wc = 0; // white_count
    for(long long i = 0; i < G[now].size(); i++){
        edge e = G[now][i];
        if(Check[e.to]){
            if(BF[e.to]) bc++;
            else wc++;
        }
    }
    if(bc > 0 and wc == 0){
        for(long long i = 0; i < G[now].size(); i++){
            if()
        }
    }else{

    }

}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n;
    for(long long i = 0; i < n - 1; i++){
        long long u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        G[u].push_back({w, v});
        G[v].push_back({w, u});
    }

    bool fff = true; // first?
    for(long long i = 0; i < n; i++){
        if(Check[i]) continue;
        if(G[i].size() >= 2){
            if(fff){
                dfs_first(i);
                fff = false;
            }else{
                // dfs_other?
            }
        }
    }

    return 0;
}

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

long long const N = 100010;

long long n;
struct edge {
    long long cost, to;
};
vector<edge> G[N];

vector<bool> BF(N);
vector<bool> C(N);
vector<bool> Color(N);

struct UnionFind{
    vector<long long> par;
    UnionFind(int NN) : par(NN){
        for(long long i = 0; i < NN; i++){
            par[i] = -1;
        }
    }
    long long root(int x){
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    void unite(long long x, long long y){
        long long rx = root(x);
        long long ry = root(y);
        if(rx == ry) return;
        else{
            if(par[rx] > par[ry]) swap(rx, ry);
            par[rx] += par[ry];
            par[ry] = rx;
       }
    }
    bool same(int x, int y){
        return root(x) == root(y);
    }
    void check(){
        for(auto x : par){
            cout << x << " ";
        }
        cout << endl;
    }
};

void dfs1(long long now, UnionFind &uf, map<long long, bool> &mp){
    C[now] = true;
    long long gc = 0; // gusu_count
    for(long long i = 0; i < G[now].size(); i++){
        edge e = G[now][i];
        if(e.to % 2 == 0) gc++;
    }
    if(gc >= (long long)G[now].size() / 2){
        for(long long i = 0; i < G[now].size(); i++){
            edge e = G[now][i];
            if(e.cost % 2 == 0){
                uf.unite(now, e.to);
                C[e.to] = true;
            }
        }
        mp[uf.root(now)] = true;
    }else{
        for(long long i = 0; i < G[now].size(); i++){
            edge e = G[now][i];
            if(e.cost % 2 != 0){
                uf.unite(now, e.to);
                C[e.to] = true;
            }
        }
        mp[uf.root(now)] = false;
    }
}

void dfs2(long long now, UnionFind &uf, map<long long, bool> &mp){
    // long long gc1 = 0, oc1 = 0; // guusuu_counst
    C[now] = true;
    long long cnt = 0;
    for(long long i = 0; i < G[now].size(); i++){
        edge e = G[now][i];
        if(C[e.to]){
            if(mp[uf.root(e.to)]){
                if(e.cost % 2 == 0){
                    uf.unite(now, e.to);
                    C[e.to] = true;
                }else{
                    mp[e.to] = false;
                    C[e.to] = true;
                }
            }else{
                if(e.cost % 2 != 0){
                    uf.unite(now, e.to);
                    C[e.to] = true;
                }else{
                    mp[e.to] = true;
                    C[e.to] = true;
                }
            }
        }else{
            cnt++;
        }
    }
    if(cnt == G[now].size()){
        dfs1(now, uf, mp);
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n;
    for(long long i = 0; i < n - 1; i++){
        long long u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        G[u].push_back({w, v});
        G[v].push_back({w, u});
    }

    map<long long, bool> mp; // true -> gusu
    UnionFind uf(n);

    bool ff = true;
    for(long long i = 0; i < n; i++){
        if(G[i].size() >= 2){
            if(ff){
                dfs1(i, uf, mp);
                ff = false;
            }else{
                if(C[i]) continue;
                dfs2(i, uf, mp);
            }
        }
    }
    for(auto x : mp){
        cout << x.first << ' ' << x.second << endl;
    }

    return 0;
}