牛客周赛 Round 104 F

注意到不动点个数等价于数组的Mex，使用树上启发式合并(DSU on Tree) 统计每个子树的Mex累加即可。

///*****Sellaris*****///
#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second

typedef unsigned long long ull;
typedef std::pair<int,int> pii;

using namespace std;

const int maxn=3e5+10;
const int mo=1e9+7;

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f;
}

int a[maxn];

int n,m;
vector<int> v[maxn];
ll ans=0;
int mex[maxn];
set<int> s[maxn]; 
void dfs(int u,int fa){
	s[u].insert(u);
	mex[u]=1;
	for(int to:v[u]){
		if(fa==to){
			continue;
		}
		dfs(to,u);
		if(s[to].size()>s[u].size()){
			swap(s[to],s[u]);
		}
	}
	for(int to:v[u]){
		if(fa==to){
			continue;
		}
		for(auto x:s[to]){
			s[u].insert(x);
		}
		s[to].clear();
		mex[u]=max(mex[u],mex[to]);
	}
	while(s[u].find(mex[u])!=s[u].end()){
		mex[u]++;
	}
	ans+=1ll*(mex[u]-1);
}
inline void solve(){
	n=read();
	for(int i=1;i<=n-1;i++){
		int x=read(),y=read();
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(n,0);
	cout<<ans<<"\n";
}

signed main(){
	int t=1;
	for(int i=1;i<=t;i++){
		solve();
	}
    return 0;
}