CF1695D2

Sellaris · 2022-07-03 21:50:27 · 题解

• 首先，将原问题抽象为另一个等价命题：

  在一颗无根树上选择 k 个点。树上每个点到这 k 个点的距离构成一个 k 维向量。求得最小的 k 使得每个向量都不相同。

• 于是考虑坐标会相同的的情况，以某点为根，有两棵子树没有选择的点的时候向量会相同。于是从原树中的所有度为 1 的点往上走，给度数 2 大的点打标记。又因为有一颗子树可以不选择，所以把叶子数减去有标记的点就是答案了。线性复杂度。

• 记得把链判掉。

• 代码：

//#pragma once
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
//#include <bits/extc++.h>
#define ll long long
using namespace std;
//using namespace __gnu_pbds;
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; //x=(x<<1)+(x<<3)+(ch^48);
}
const int maxn=1e5+10;
int n,ans;
vector<int> vec[maxn<<1];
bool vis[maxn];

int dfs(int u,int fa){
    if(vec[u].size()>2) return u;
    for(auto v:vec[u]) if(v!=fa) return dfs(v,u);
    return u;
}

inline void solve(){
    n=read();ans=0;
    for(int i=1;i<=n;i++) vec[i].clear(),vis[i]=0;
    if(n==1) {
        puts("0");return;
    }
    for(int i=1,u,v;i<n;i++)
        u=read(),v=read(),vec[u].push_back(v),vec[v].push_back(u);
    for(int i=1;i<=n;i++)
        if(vec[i].size()==1) vis[dfs(i,0)]=true,ans++;
    for(int i=1;i<=n;i++) if(vis[i]) ans--;
    if(ans==0) puts("1");
    else printf("%d\n",ans);
}
int main(){
    int t=read();
    while(t--){
        solve();
    }
    return 0;
}