Codeforces 1283 F DIY Garland ——想法

本文主要是介绍Codeforces 1283 F DIY Garland ——想法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

现在有n个点，第i个点的权值为$2^i$，现在有n-1条边使得这些点组成一棵树，边的权值是它连接的子树的权值和。现在按照边的权值从大到小给你每条边的父节点，让你输出根节点的下标以及输出输入顺序每条边所连接的两个点

题解：

自顶向下我觉得做不了，但是反过来一想自底向上很简单，首先我们处理出所有未出现过的点是什么，然后最后一条边连接的一定是最小的那个点。有了这个思路我们就可以很容易的想到如果我们从后往前做，那么当前的点连接的一定是可供选择的点中的子树的值最小的那个。由于每个点的值是2的幂次，于是我们只需要记录当前点子树中最大的点的值是什么即可。那么什么是可供选择的点？首先可供选择的点一定是未在输入中出现过的点，然后如果当前点还在前面的输入中出现过，那么就证明这个点还连着值更大的儿子，那么这个点就不能被判为可供选择的点。

#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
const int N=2e5+5;
int vis[N];
struct node
{int id,mx;bool operator< (const node& a)const{return mx>a.mx;}
};
priority_queue<node>Q;
int fa[N];
pa ans[N];
int main()
{int n;scanf("%d",&n);for(int i=1;i<n;i++)scanf("%d",&fa[i]),vis[fa[i]]++;for(int i=1;i<=n;i++)if(!vis[i])Q.push({i,i});for(int i=n-1;i;i--){node now=Q.top();Q.pop();ans[i]={fa[i],now.id};vis[fa[i]]--;if(fa[i]!=fa[1]&&!vis[fa[i]])Q.push({fa[i],max(now.mx,fa[i])});}printf("%d\n",fa[1]);for(int i=1;i<n;i++)printf("%d %d\n",ans[i].first,ans[i].second);return 0;
}

这篇关于Codeforces 1283 F DIY Garland ——想法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---