题解：P15247 [WC2026] 画树

chenbs · 2026-02-19 12:46:42 · 题解

官方题解做法，可能有一点不同。

不妨设树的根都是 1。

part1. 求解 k_{\min}

定义 d(u) 为 T 中 u 的度数，d'(u) = d(u) + \sum [p_i = u] + \sum [e_i = u]，即将每一对铅笔橡皮看成一条边后的度数。

注意到 d'(u) 的奇偶性不变，这个可以直接推式子证明。也就是说，一对铅笔橡皮只能改变至多两个点的 d(u) 的奇偶性。

记有 \text{cnt} 个点在两棵树中度数奇偶性不同，则 k_{\min} \ge \frac{\text{cnt}}{2}，下面尝试取到它。

part2. 方案构造

首先操作是可逆的，考虑把 T' 反向变成 T，问题转化为：

初始你可以在把若干对铅笔橡皮放在任意位置（铅笔和橡皮可以不用在一起），然后对 T' 执行若干次题意中的操作，最终要让 T' 变成 T，并且每对铅笔橡皮在同一位置。

基本操作一：如果一对铅笔橡皮在同一位置，可以不影响树的形态任意同步移动。

基本操作二：定义 \operatorname{combine}(t, p_t, e_t) 表示将一对铅笔橡皮移动到任意同一个节点的操作组合。考虑添加一条虚边 (p_t, e_t) 后形成的基环树，我们只需要按下图方法移动铅笔橡皮，就可以将虚边调整到环上的任意位置。找到一个基环上有子树的节点，把铅笔橡皮按照下图方案都移动过去即可。

如果基环树就没有子树，称这次 \operatorname{combine} 失败，我们会在下文解决这个问题。

将方案分成两步。

part 2.1 调整奇偶性

初始显然是把 \frac{\text{cnt}}{2} 对铅笔橡皮分配给需要调整度数奇偶性的 \text{cnt} 个点上。如果 T' 是一条链，并且链的两端都需要调整，那么 \operatorname{combine} 可能会失败。这种情况下，一定还有其它点需要调整，可以换一种分配方式，或者交换调整顺序。

然后依次把每对铅笔橡皮执行 \operatorname{combine} 即可。

part 2.2 调整树形态

这个部分只需要一对铅笔橡皮。

考虑 T 的一个叶子 x，x 在 T' 中的度数一定是奇数。按照下图方法，可以把 x 在 T' 中的度数降到 1（下图方法每执行一次，度数降低 2）。

然后设 x 在 T' 中唯一的邻居为 c，在 T 中的父亲为 y。先将铅笔橡皮都移动到 x，再把铅笔移到 y、橡皮移到 c，最后 \operatorname{combine}(1,y,c) 就完成了一次换父亲。

假装把 x 删掉，对剩下的部分不断重复上述操作，本题就做完了。

注意到 T 至少有一个点度数为 1，所以 T' 加入铅笔橡皮的边形成的基环树中一定有一个点度数为奇数，因此 \operatorname{combine} 不会失败。

操作次数 O(n^2)，但是数据随机完全跑不满。

#include<bits/stdc++.h>
using namespace std;
void setting(int k, vector<int> p);
void alter(int t, int x, int y);
void init(int c, int t) {}
struct OP {
    int id,p1,p2,e1,e2;
} op[114514];
int opc;
int p[105], e[105];
vector<int> G[205], G2[205];
void alter2(int t, int x, int y) {
    if(p[t]==x) return;
    op[++opc]={t,p[t],x,e[t],y};
    G2[p[t]].push_back(x), G2[x].push_back(p[t]);
    G2[e[t]].erase(find(G2[e[t]].begin(), G2[e[t]].end(), y));
    G2[y].erase(find(G2[y].begin(), G2[y].end(), e[t]));
    p[t]=x, e[t]=y;
}
int deg[205], deg2[205], a[205], cnt, vis[205], path[205], dep;
int dfs(int x, int y, int d) {
    vis[x]=1, path[d]=x;
    if(x==y) return dep=d, 1;
    for(auto i:G2[x]) if(!vis[i] && dfs(i,y,d+1)) return 1;
    vis[x]=0;
    return 0;
}
int combine(int id, int x, int y) {
    if(x==y) return 1;
    memset(vis,0,sizeof vis);
    dfs(y,x,1);
    int ok=0;
    for(int i=1; i<=dep; i++)
        for(auto j:G2[path[i]])
            if(!vis[j])
                ok=1;
    if(!ok) return 0;
    for(int i=1; i<=dep; i++) {
        int z=-1;
        for(auto j:G2[path[i]])
            if(!vis[j])
                z=j;
        if(~z) {
            alter2(id, z, z);
            return 1;
        }
        alter2(id, path[i], path[i+1]);
    }
}
void hide(int x) {
    for(auto y:G2[x]) G2[y].erase(find(G2[y].begin(), G2[y].end(), x));
    G2[x].clear();
}
int tmp[205];
void dfs2(int x, int fa) {
    for(auto y:G[x]) {
        if(y==fa) continue;
        dfs2(y,x);
    }
    if(x==1) return;
    int sz=0;
    for(auto y:G2[x]) tmp[++sz]=y;
    for(int i=2; i<=sz; i+=2) {
        alter2(1, tmp[i], tmp[i]);
        alter2(1, tmp[1], x);
        alter2(1, tmp[i+1], tmp[i+1]); 
    }
    if(fa!=tmp[1]) {
        alter2(1, x, x);
        alter2(1, fa, tmp[1]);
        hide(x);
        combine(1, fa, tmp[1]);
    } else {
        hide(x);
    }
}
void paint(int n, vector<int> u, vector<int> v) {
    opc=0;
    for(int i=1; i<=n; i++) deg[i]=deg2[i]=0, G[i].clear(), G2[i].clear();
    for(int i=0; i<n-1; i++) {
        G[u[i]].push_back(v[i]), G[v[i]].push_back(u[i]);
        deg[u[i]]++, deg[v[i]]++;
    }
    for(int i=n-1; i<2*n-2; i++) {
        G2[u[i]].push_back(v[i]), G2[v[i]].push_back(u[i]);
        deg2[u[i]]++, deg2[v[i]]++;
    }
    cnt=0;
    for(int i=1; i<=n; i++)
        if((deg[i]&1)!=(deg2[i]&1))
            a[++cnt]=i;
    if(!cnt) p[1]=e[1]=1;
    for(int i=1; i<=(cnt>>1); i++) {
        p[i]=a[i*2-1], e[i]=a[i*2];
        if(!combine(i, p[i], e[i])) {
            swap(a[i*2-1], a[i*2+1]), swap(a[i*2], a[i*2+2]);
            p[i]=a[i*2-1], e[i]=a[i*2];
            combine(i, p[i], e[i]);
        }
    }
    dfs2(1,0);

    // 倒着输出最终答案
    int mx=0;
    for(int i=1; i<=opc; i++) mx=max(mx, op[i].id);
    vector<int> vec;
    for(int i=1; i<=mx; i++) vec.push_back(p[i]);
    setting(mx, vec);
    for(int i=opc; i>=1; i--) alter(op[i].id, op[i].e1, op[i].p1);
}