codeforces 1041 e 构造

Codeforces 1041 E

构造题。

给出一种操作，对于一棵树，去掉它的一条边。那么这颗树被分成两个部分，两个部分的分别的最大值就是这次操作的答案。

现在给出一棵树所有操作的结果，问能不能构造这样一颗树，可以的话输出它。

反正就是看每个数出现了几次，然后形成一条链，从这个数开始，依次减小，链向N。

这样处理每个数，就行了。中间一旦有冲突(不能形成链了),直接NO。

#include <bits/stdc++.h>

using namespace std;

map<int,int> mp;

bool vis[1005];

struct node {

    int l,r;

};

vector<node> ans;

int main() {

    int n;

    scanf("%d",&n);

    memset(vis,false,sizeof(vis));

    int a,b;

    for(int i = 1; i < n; i++) {

        scanf("%d %d",&a,&b);

        mp[a]++;

        mp[b]++;

    }

    if(mp[n] != n - 1) {

        printf("NO\n");

        return 0;

    }

    node ad;

    for(int i = 1; i < n; i++) {

        if(i - mp[i] + 1 < 1) {

            printf("NO\n");

            return 0;

        }

        int val = i;

        if(!mp[val]) {

            continue;

        }

        vis[val] = true;

        if(mp[val] == 1) {

            ad.l = val;

            ad.r = n;

            ans.push_back(ad);

            continue;

        }

        for(int j = 1; j < mp[i]; j++) {

            int rr = val;

            while(vis[val]) {

                val--;

                if(val < 1) {

                    printf("NO\n");

                    return 0;

                }

            }

            vis[val] = true;

            ad.l = val;

            ad.r = rr;

            ans.push_back(ad);

        }

        ad.l = n;

        ad.r = val;

        ans.push_back(ad);

    }

    printf("YES\n");

    for(int i = 0; i < ans.size(); i++) {

        printf("%d %d\n",ans[i].l,ans[i].r);

    }

    return 0;

}

巴特西

codeforces 1041 e 构造

最新文章

热门文章