Codeforces 1325 C. Ehab and Path-etic MEXs（贪心构造）

题意：

给一颗树，有 $n$ 个顶点，给这个树的边分别编号为 $0(n-2)$，问怎样编使得对于树上任意两点 $u,v$ 的最大 $mex(u,v)$ 值最小。$mex(u,v)$ 表示由 $u$ 到 $v$ 点的简单路径的长度构成的集合中，没有出现的最小非负整数。
很简单的一个贪心策略，我们只要找到一个度数大于2的节点，和他相连的边放置 $0,1，2...$ 这样即可。

AC代码：

const int N = 2e5 + 10;
vector<pair<int, int>> v[N];
int ans[N];
int n, cnt;
int x, y;

int main()
{
    sd(n);
    rep(i, 1, n - 1)
    {
        sdd(x, y);
        v[x].pb(make_pair(y, i));
        v[y].pb(make_pair(x, i));
    }
    cnt = 1;
    rep(i, 1, n)
    {
        if (v[i].size() > 2)
        {
            for (auto j : v[i])
                ans[j.se] = cnt++;
            break;
        }
    }
    rep(i, 1, n - 1)
    {
        if (ans[i] == 0)
            ans[i] = cnt++;
        pd(ans[i] - 1);
    }
    return 0;
}

最后

以上就是开放机器猫为你收集整理的Codeforces 1325 C. Ehab and Path-etic MEXs（贪心构造）的全部内容，希望文章能够帮你解决Codeforces 1325 C. Ehab and Path-etic MEXs（贪心构造）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。