[构造][树][贪心] codeforces 1041E Tree Reconstruction

http://codeforces.com/contest/1041/problem/E

比赛完5min想到了ac做法emmmm

并没有看懂官方题解，NO的判别其实很简单，只要有b不是n的情况就NO，因为不管怎么分都一定会有一个n。YES的情况怎么构造？我自己的做法是把n作为根节点，把条件排序后从小到大考虑：如果一个点出现了一次，那么就连一条从根节点到这个点的边，并且把这个点标记为用过的；如果出现了多次，那么就到前面找没有标记过的点找一个最小的插到当前点和他的父节点之间，并且把找到的点也标记为用过的。

所以为什么是正确的？首先按照a排序后可以发现如果一个数字重复出现了那么一定是从第ai个往前重复，如1 3 3 4，这个重复的3一定是从第3个往前延申，按照我的构造方法，如果不是这样那就不可能满足要求，因为3和5之间的路上的节点一定是全是小于3的数字，而且以3为根的子树我这里直接让他为空。这样的话总可以在前面找到足够数量的数字来插入到3的这一条链上（忽然感觉说不清楚了但是这么构造一定是对的emmmmm
wa的话感觉可能是当时很饿然后树上的插入操作和标记都写错n次，神奇的是每次都能通过前30个test然后被3x刷掉。。

#include

using namespace std;

typedef long long LL;
const int maxn=1e3+5;
const int mod=1e9+7;

struct node
{
    int id,fa;
    setch;
    node(){id=fa=0;ch.clear();}

}ns[maxn];

pair ps[maxn];
bool vis[maxn];
int ans=0;

void dfs(int x)
{
    if(!ns[x].ch.size())return;
    for (set::iterator it=ns[x].ch.begin();it!=ns[x].ch.end();it++)
    {
        ps[++ans]=make_pair(x,(*it));
        dfs((*it));
    }
}

int main()
{
    int n,ta,tb;
    cin>>n;
    for (int i=1;i>ta>>tb;
        if(ta>tb)
            swap(ta,tb);
        if(tb!=n)
        {
            puts("NO");
            return 0;
        }
        ps[i].first=ta,ps[i].second=tb;
    }

    sort(ps+1,ps+n);
    for (int i=1;i