Tree with Small Distances

Tree with Small Distances

分析

居然还要看按照深度进行操作，大意了，没有学
其实就是一个贪心。因为如果这个点距离根节点超过2，只需要考虑边加在哪里。有三个选择：父节点，自己，子节点。选择父节点更优。记录两个数组：

vis[i]:此节点是否与根节点直接相连
op[i]:此节点与根节点的距离是否大于2

每次从深度最大的一个节点里选出一个，如果他与根节点的距离大于2并且他的父节点并没有与根节点直接相连。那么就加一条的边，同时更新周围节点的标记。还有一些预处理细节。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N=2e5+10;

int n,tot,ans;
int h[N],nex[N<<1],ver[N<<1],dep[N],fa[N];

bool vis[N],op[N];

struct nk
{
    int x;
    bool operator < (const nk &b)const
    {
        return dep[x]<dep[b.x];//深度从大到小 
    }
    nk(int xx):x(xx){}
};priority_queue<nk>q;

inline void add(int x,int y)
{
    nex[tot]=h[x];
    ver[tot]=y;
    h[x]=tot++;
}

inline void dfs(int u,int v)
{
    dep[u]=dep[v]+1;fa[u]=v;
    for (int i=h[u];~i;i=nex[i])
    {
        int j=ver[i];
        if(j==v) continue;

        dfs(j,u);
    }
}

int main()
{
    memset(h,-1,sizeof(h));
    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }

    vis[1]=1;//相连
    for (int i=h[1];~i;i=nex[i]) vis[ver[i]]=1;
    dfs(1,0);

    for (int i=1;i<=n;i++) q.push(i);

    while(!q.empty())
    {
        nk u=q.top();q.pop();
        int x=u.x;
        if(!op[x])
        {
            if(vis[x]||vis[fa[x]]) continue;
            ans++;vis[fa[x]]=1;
            for (int i=h[fa[x]];~i;i=nex[i]) op[ver[i]]=1;
        }
    }

    printf("%d\n",ans);

    return 0;
}