CF1338B Edge Weight Assignment 题解

题目链接：CF1338B Edge Weight Assignment

题意：

给定一棵 $n(3 \le n\le 10^5)$ 个点的无根树

要求给每条边分配一个正整数权值，使得任意两个叶子节点之间路径上的边权异或值为 $0$。

求最少要多少种不同权值，以及最多可以使用多少种不同权值。 填入的边权值可以为任意大。

直觉告诉我们，第二个问题的答案和第一个问题的答案高度相关（废话）。

先找一个度数不为 $1$ 的点作根，那么题目就转化为：叶子节点到根的路径上边权异或值相同。

如果所有这样的路径长度的奇偶性都相同，那么可以全部填 $1$ 。

否则我们可以…等等，好像并不能靠填 $0,1$ 到达这个目的，怎么办呢？（写完才发现是正整数）

观察样例可以发现，$\left((01)_2 \land (10)_2\right) \oplus (11)_2 = 0$ ，也就是说我们可以用 $1,2,3$ 来填。

对于长为偶数的路径就填 $1,2,1,\cdots,1,2$ ，对于奇数的路径，就在最后一条边填 $3$ 。

那么第一个问题就解决了，我们来考虑第二个问题。

同样观察样例可以发现，如果树上某一条简单路径不包含任何一个叶子节点，

那么我们可以较为随意地填上面的数，例如将 $2,1,2$ 换成 $2,4,7$ ，这一部分很容易用 dp 统计。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int res, num, pos = 1, head[N], in[N], dp[N];
struct Edge { int u,v,next; } e[N << 1];
void addEdge(int u, int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
int dfs(int u, int fa, int k)
{
    if(in[u] == 1) { res += k; ++num; dp[u] = -1; return 1; }
    dp[u] = 0; int tmp = 0;
    for(int i = head[u], v; i; i = e[i].next)
        if((v = e[i].v) != fa) { tmp |= dfs(v, u, k ^ 1); dp[u] += dp[v] + 1; }
    if(tmp) ++dp[u];
    return 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, rt; cin >> n;
    for(int i = 1, u,v; i < n; i++)
    {
        cin >> u >> v; ++in[u]; ++in[v];
        addEdge(u, v); addEdge(v, u); 
    }
    for(int i = 1; i <= n; i++) if(in[i] > 1) rt = i;
    dfs(rt, rt, 1); cout << (res % num ? 3 : 1) << ' ' << dp[rt] << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/gyh20/solution-cf1338b

---

放个图