Submission #41787355

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 2e5+10;

int n,a[MAXN],b[MAXN];
vector<int>e[MAXN];

int fa[MAXN],sz[MAXN],cnt[MAXN],ret;

int V(int x){
	return min(sz[x],cnt[x]);
}
int find(int x){
	return (fa[x] == x) ? (x) : (find(fa[x]));
}
typedef array<int,2> pr;
vector<pr>opt;

void merge(int x,int y){
	x=find(x);y=find(y);
	if(x==y){
		ret -= V(x);
		cnt[x] ++;
		ret += V(x);

		opt.push_back({x,-1});
	}else{
		if(sz[x] > sz[y])swap(x,y);
		ret -= V(x);ret -= V(y);
		fa[x] = y;sz[y] += sz[x];cnt[y] += cnt[x]+1;
		ret += V(y);

		opt.push_back({x,y});
	}	
}
void roll_back(){
	assert(opt.size());
	pr tmp = opt.back();opt.pop_back();
	int x = tmp[0],y = tmp[1];
	if(y==-1){
		ret -= V(x);
		cnt[x] --;
		ret += V(x);
	}else{
		ret -= V(y);
		fa[x] = x;sz[y] -= sz[x];cnt[y] -= (cnt[x]+1);
		ret += V(x);ret += V(y);
	}
}

int ans[MAXN];

void dfs(int u,int fa){
	for(auto v:e[u])if(v!=fa){
		merge(a[v],b[v]);
		ans[v] = ret;
		dfs(v,u);
		roll_back();
	}
}

int main(){
	ios::sync_with_stdio(false);

	cin>>n;
	rep(i,1,n)cin>>a[i]>>b[i];

	rep(i,1,n)fa[i] = i,sz[i] = 1;

	rep(i,1,n-1){
		int u,v;cin>>u>>v;
		e[u].push_back(v);e[v].push_back(u);
	}

	merge(a[1],b[1]);
	dfs(1,0);

	rep(i,2,n){
		cout<<ans[i]<<" ";
	}

    return 0;
}

Submission Info

Judge Result