AtCoder Beginner Contest 396 (E-F)

后面补G

E-Min of Restricted Sum

当一个点值确定时，整个联通块的值也确定了，由此可以判断是否有解
同理，对于一个联通块内的根节点，其点值的二进制下的每位就独立的决定了其它点在该位的值，也就是说，若根节点值在一个二进制位下为0，可以决定其它点值在当前位下是0还是1,而若根节点在该位是1，则其他点值在该位就要取反

思路

对于一个连通块的根节点，先假设该点的值为0
dfs判断一下连通块是否合法，如合法，再统计连通块内其他点在每一位上的1与0的个数
若1的个数大于0的个数，为了使得对答案的值更小，我们选择根节点的值在当前二进制位下为1,否则为0
[code]const int N=2e5+5;vectore[N];int val[N],vis[N],ans[N];vectornw;void dfs(int u){    vis=1;    nw.push_back(u);    for(auto [v,w]:e){        if(vis[v]){            if((val^w)!=val[v]){                coutn>>m;    rep(i,1,m){        int u,v,w;cin>>u>>v>>w;        e.push_back({v,w});        e[v].push_back({u,w});    }    rep(i,1,n){        if(vis) continue;        dfs(i);        int tmp=0;        rep(j,0,30){            int cnt0=0,cnt1=0;            for(auto u:nw){                if(val>>j&1) cnt1++;                else cnt0++;            }            if(cnt1>cnt0) tmp|=1m;    rep(i,1,m){        int u,v,w;cin>>u>>v>>w;        e.push_back({v,w});        e[v].push_back({u,w});    }    rep(i,1,n){        if(vis) continue;        dfs(i);        int tmp=0;        rep(j,0,30){            int cnt0=0,cnt1=0;            for(auto u:nw){                if(val>>j&1) cnt1++;                else cnt0++;            }            if(cnt1>cnt0) tmp|=1