兔子

dottle · 2022-09-05 19:12:07 · 题解

我们考察整棵树上编号最大的点 X。对于经过 X 的所有路径，都应当选取 X 作为最大值。去掉 X，将树切成了若干子树，递归进子树内解决原问题。然后对于这些子树，如果有至少两个子树内还有没进三元组的点，就他们和 X 作为一个三元组。

直接做是 n^2 的，我们不妨逆序地考虑。从小到大地加入每个点，每次加入点的时候把和它相邻的、已经加入了的点合并在一起。维护每一个连通块的最大三元组个数和总大小，未匹配点的个数可以根据前两个信息方便地计算。

时间复杂度 O(n\alpha (n))，其中 \alpha(n) 是并查集复杂度。

#include<bits/stdc++.h>
const int N=1000050;
using namespace std;

int n,res;
int fa[N],rest[N];
int gf(int k){return k==fa[k]?k:fa[k]=gf(fa[k]);}
vector<int> e[N];

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)fa[i]=i,rest[i]=1,e[i].clear(),res=0;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        e[max(x,y)].push_back(min(x,y));
    }
    for(int k=1;k<=n;k++){
        int c=0;
        for(auto to:e[k]){
            c+=!!rest[gf(to)];
            rest[k]+=rest[gf(to)];
            fa[gf(to)]=k;
        }
        if(c>=2)rest[k]-=3,res++;
    } 
    cout<<res<<endl;
}

main(){
    ios::sync_with_stdio(false);
    int _T=1;cin>>_T;
    while(_T--)solve();
}