Submission #1161101

---

Source Code Expand

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

template<class graph_type> int compute_subtree_size(const graph_type &graph,const vector<bool> &centroid,vector<int> &subtree_size,int u,int p){
    int c=1;
    for(const auto &edge:graph[u]){
        int v=edge.to;
        if(v==p or centroid[v]) continue;
        c+=compute_subtree_size(graph,centroid,subtree_size,v,u);
    }
    subtree_size[u]=c;
    return c;
}

//tは連結成分全体のサイズ
//u以下で,削除により残る最大の部分木の頂点数が最小となる頂点の,(残る最大の部分木の頂点数,頂点番号)のペアを返す
template<class graph_type> pair<int,int> search_centroid(const graph_type &graph,const vector<bool> &centroid,const vector<int> &subtree_size,int u,int p,int t){
    pair<int,int> res=make_pair(inf,-1);
    int s=1,m=0;
    for(const auto &edge:graph[u]){
        int v=edge.to;
        if(v==p or centroid[v]) continue;
        res=min(res,search_centroid(graph,centroid,subtree_size,v,u,t));
        m=max(m,subtree_size[v]);
        s+=subtree_size[v];
    }
    m=max(m,t-s);
    res=min(res,make_pair(m,u));
    return res;
}

struct edge{
    int to,cost;
};

void solve(){
    int n,x;
    cin >> n >> x;
    vector<vector<edge>> graph(n);
    rep(i,0,n-1){
        int x,y,c;
        cin >> x >> y >> c;
        --x;
        --y;
        graph[x].push_back(edge({y,c}));
        graph[y].push_back(edge({x,c}));
    }

    map<int,i64> count;
    function<void(int,int,int)> dfs=[&](int u,int p,int s){
        ++count[s];
        for(edge &e:graph[u]){
            if(e.to==p) continue;
            dfs(e.to,u,s^e.cost);
        }
    };
    dfs(0,-1,0);
    i64 ans=0;
    for(auto &p:count){
        if(p.first==(p.first^x)) ans+=(p.second-1)*p.second/2;
        else ans+=p.second*count[p.first^x];
        count[p.first^x]=0;
    }
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}

Submission Info

Judge Result