CodeForces-765E Tree Folding

题意

给出一棵树，若两条链具有同一个端点、长度相同、并且每个链上结点不能邻接有不属于这条链的结点(除了那个相同的端点)，则这两条链可以在一次操作中合并在一起，如下图。问若干次操作之后是否能令这棵树变成一条链，能的话这条链最短是多长。

思路

如果最终能合并成一条链，说明链上结点原有的分支都是相同长度，能合并在一起的。那么考虑拓扑排序，若$u$与$v$关联，且$v$的拓扑序在$u$之前，统计$u$在$v$方向的分支长度，放进$u$的集合set，这样相同长度的分支在set里都表现为一个数字，说明它们能合并成一条链。题目还要求链上结点不能邻接有不属于这条链的结点，所以set里元素个数为1的才能放进拓扑排序的队列(这里我们把原图度数为1的结点的set先放进一个元素0，表示它们有长度为0的分支)。若这棵树能合并为一条链，所有结点的set最终只有1个元素，拓扑序最后的那个结点可能有2个元素(因为是最后一个结点，即使其两端分支长度不同也是一条链)，把合并完的链一直折叠直到长度为奇数就是最短链了。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <queue>
using std::queue;
using std::vector;
using std::set;
using std::max;
const int N = 200010;
bool vis[N];
int deg[N];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        vector<int> G[n+10];
        set<int> se[n+10];
        memset(vis, 0, sizeof(vis));
        memset(deg, 0, sizeof(deg));
        for (int i = 0, u, v; i < n - 1; i++) {
            scanf("%d %d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
            deg[v]++, deg[u]++;
        }
        queue<int> que;
        for (int i = 1; i <= n; i++) {
            if (G[i].size() == 1) {
                que.push(i);
                se[i].insert(0);
            }
        }
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            vis[u] = true;
            for (auto v : G[u]) {
                if (vis[v]) continue;  // u的拓扑序在v之前，我们不统计v的这个分支
                se[v].insert(*se[u].begin() + 1);
                deg[v]--;
                if (deg[v] == 1 && se[v].size() == 1) que.push(v);
            }
        }
        int ans = 0, cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (se[i].size() == 0 || se[i].size() > 2) {
                ans = -1;
                break;
            }
            if (se[i].size() == 2) {
                ans = max(ans, *se[i].begin() + *se[i].rbegin());
                cnt++;
            }
            else ans = max(ans, *se[i].begin());
        }
        if (cnt > 1) ans = -1;
        while (!(ans & 1)) ans >>= 1;
        printf("%d
", ans);
    }
    return 0;
}

View Code