F题启发式合并写法题解

先将不动点问题通过每个节点编号减一，就能转化成一个以i节点为根当前子树所有节点编号的mex()问题，通过将当前节点的所有子节点集合合并，就能得到当前节点为根集合，通过map维护其mex值，直接合并的时间复杂度最大为n^2（也就是形成一条链的形式）,使用启发式合并后可将时间复杂度优化至nlogn，代码如下：

#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <cstring>
#include <cmath>
#include <random>
// #define int long long 
#define ll long long 
#define ull unsigned long long 
#define pb push_back
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define fi first
#define se second
#define rt return

using namespace std;

mt19937_64 rnd(time(0));
typedef pair<int,int> PII;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,-1,1};

// const int M = 400010,P = 998244353;
// const int M = 400010,P = 1e9+7;
// int e[M],ne[M],h[M],idx;
// void add(int a,int b){e[idx] = b,ne[idx] = h[a],h[a] = idx++;}
// int lowbit(int x){return x&-x;}
// int lcm(int a,int b){return a*b/__gcd(a,b);}
// vector<vector<int>>a(n+1,vector<int>(m+1,0)); n*m的二维数组
// vector<vector<vector<int>>> dist(n+1,vector<vector<int>>(m+1,vector<int>(k+1, INF))); n*m*k的三维数组

const int N = 500010;
map<int,int>mp[N];
vector<int>p[N];
int f[N];
int cnt[N];
int t[N];
ll res = 0;

void merge(int &x,int &y){
	
	if(x == y) return;
	if(cnt[x] > cnt[y]) swap(x,y);
	for(auto xx:mp[x])
		mp[y][xx.fi]++;
	while(mp[y].count(f[y])) f[y]++;
	cnt[y]+=cnt[x];
	cnt[x] = 0;
	mp[x].clear();
	
}

void dfs(int u,int fa){
	
	int j = -1;
	for(auto xx:p[u]){
		if(xx == fa) continue;
		dfs(xx,u);
		if(j == -1 || cnt[t[xx]] > cnt[t[j]]) j = xx;
 	}
 	if(j!=-1) swap(t[j],t[u]);
 	for(auto xx:p[u]){
 		if(xx == fa) continue;
 		merge(t[xx],t[u]);
 	}
 	while(mp[t[u]].count(f[t[u]])) f[t[u]]++;
	res+=f[t[u]];
}

void slove(){
	    
 	int n;
 	cin >> n;
 	for(int i=0;i<=n;i++) cnt[i] = 1,mp[i][i] = 1;
 	for(int i=0;i<=n;i++) t[i] = i;
 	for(int i=1;i<n;i++){
 		int u,v;
 		cin >> u >> v;
        u--,v--;
 		p[u].push_back(v);
 		p[v].push_back(u);
 	}
 	dfs(n-1,-1);
 	cout << res << '\n';
 	
}
 
signed main(){
	
	std::ios::sync_with_stdio(0);
  	std::cin.tie(0);
	int t = 1;
	//多组
	// cin >> t;
	while(t--) slove();
	
	//养成好习惯^_^
	return 0;
	
}