cf 646 E. Tree Shuffling

欲張って、aiの最小の点を選んで下に遍歴して、それから最大の交換回数をします.残りの(1つの0または1つの1つにルートノードが存在する)をこの過程を続ければよい.私たちは歩いた点が必ず行かないと推測できる(歩いて行くともっと優れないに違いない)

#include
using namespace std;
typedef long long ll;
const int N = 2e5+10;
ll a[N];
int fa[N],b[N],c[N],cur,h[N],nex[N<<1],to[N<<1],vis[N],re[N][2];
ll ans;
void add_edge(int x,int y){
	to[++cur]=y;nex[cur]=h[x];h[x]=cur;
}
void dfs(int u,int f){
	fa[u]=f;
	for(int i = h[u]; i; i=nex[i]){
		if(f!=to[i]){
			dfs(to[i],u);
		}
	}
}
void dfs1(int rt,int u){
	if(vis[u]) return;
	vis[u]=1;
	re[rt][0]+=(b[u]!=c[u]&&(b[u]==0));
	re[rt][1]+=(b[u]!=c[u]&&(b[u]==1));
	for(int i = h[u]; i; i = nex[i]){
		int v = to[i];
		if(v!=fa[u]&&vis[to[i]]){
			re[rt][0]+=re[to[i]][0];
			re[rt][1]+=re[to[i]][1];
		}
		if(v!=fa[u]&&!vis[to[i]]){
			dfs1(rt,v);
		}
	}
}
struct node{
	ll a;
	int b,c,id;
	bool operator