cf1695D1. Tree Queries (Easy Version)（div2）【树上问题】

传送门

题意

给定一棵树，并在树上任选一个节点 $x$ （未知），每次都可以询问树上另一指定结点 $v$ 到 $x$ 的最短路径，问最少需要几次询问，使得不论 $x$ 是哪一个结点，都可以在询问次数及之内确认该点。

脑模可以发现，如果树的形状是一条链，可以仅通过询问一次叶子结点确认。不属于该结构的第一个例子是拥有 $4$ 个结点的菊花图，假设以结点 $2$ 为菊花中心，则确认其他三个结点中的任意一个都需要经历：$1.$确定该点不是菊花中心 $2.$确定该点 两次询问。

此时若以 $2$ 为根，则结点 $1,3,4$ 均构成单独的链，可以发现增长 （ 如添加 $(4,5)$ ）其中的某条链不影响答案贡献。若在该基础上再增加 $(4,6)$ ，由于子链的个数将增多，以 $2$ 为根的答案为 $3$，但改变作为根的结点时，将影响树中的子链个数从而影响答案，使最优答案仍为 $2$ 。

因此将所有点作为根的情况都跑一遍 $dfs$ ，$link$ 为当前结点直接相连的子链个数，由此向上传递答案贡献值。

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;

const int N=2e5+10;
vector<int> g[N];

int dfs(int u,int fa){
    int cnt=0,link=0;
    for(auto v:g[u]) {
        if(v==fa) 
            continue;
        int x=dfs(v,u) ;
        if(!x)
            link++;
        cnt+=x;
    }
    cnt+=max((long long)0,link-1);
    // cout<<u<<" "<<cnt<<" "<<link<<endl;
    return cnt;
}

void solve() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) 
        g[i].clear();
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v) ;
        g[v].push_back(u) ;
    }
    int ans=n-1;
    for(int i=1;i<=n;i++){
        ans=min(ans,dfs(i,0)+1);
    }
    cout<<ans<< endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1; 
    cin>>t;
    while(t--) 
        solve();
    return 0 ;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50