【树形DP】[AtCoder Petrozavodsk Contest 001 E] Antennas on Tree

题意：

给出一颗树，在树上选择K个点，再定义一个点的权值为：
其到每一个选中节点的距离所组成的K维向量。
现在要使得所有点的权值互不相同，求最小的K

---

分析：

首先，必须明确一些性质：
对任意一个点 u $u$所有邻接点所在的联通块中，至多只有一个联通块中没有被选择点。
这就是本题的核心。

但这个性质是基于一个图的，我们要将其转移到树上，就必须解决连向祖先的联通块的影响。
其实只需要选择一个度数大于等于3的节点作为根就可以了：原因很简单，如果根的度数大于等于3，对任意一个点而言，其连向祖先的联通块中必然有点被选择，就不需要考虑祖先了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
vector<int> a[MAXN];
int n,root=-1;
int dfs(int x,int fa){
    int res=0;
    int flag=0;
    for(int i=0;i<a[x].size();i++){
        if(a[x][i]==fa)
            continue;
        int res1=dfs(a[x][i],x);
        if(res1==0&&flag==1)
            res++;
        if(res1==0&&flag==0)
            flag=1;
        res+=res1;
    }
    return res;
}
int main(){
    SF("%d",&n);
    int u,v;
    for(int i=1;i<n;i++){
        SF("%d%d",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for(int i=0;i<n;i++)
        if(a[i].size()>=3){
            root=i;
            break;
        }
    if(root==-1){
        PF("1");
        return 0;
    }
    PF("%d",dfs(root,-1));
}