分析
居然还要看按照深度进行操作,大意了,没有学
其实就是一个贪心。因为如果这个点距离根节点超过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; }