题解：CF1140G Double Tree

___Fengwenjie1___ · 2026-10-23 16:16:50 · 题解

感觉要严谨证明的话思维难度也不低啊……

主要讲一下让我困惑的初始状态的两个 DFS。

题意

CF1140G Double Tree

给定两棵同构的树 T_1,T_2，都有 n 个点。两棵树的对应点之间有连边。

给定 w_u(u\le 2n) 为其父边权值，d_u(u\le n) 为 T_1 的 u 和 T_2 的 u 之间的边的权值，q 次询问两点之间的最短路。

设 W 为边权值域。

n\le 3\times10^5\quad q\le 6\times10^5\quad W=[1,10^{12}]

思路

树上问题，很容易想到树上倍增。设 u 的 2^j 级祖先为 anc_{u,j}。

回顾，普通的树上倍增是 O(n\log n) 预处理：

然后 O(\log n) 处理查询。

那这里能不能同样处理 sum 呢？

我们发现，这里和普通的区别只有我开始的时候是在 T_1 还是 T_2，结束的时候是在 T_1 还是 T_2，并不关心中间是否反复横跳。

所以我们可以设 sum_{u,j,s,t} 表示：从 u 往上跳到 anc_{u,j}，s 为开始的时候是否在 T_2，t 为结束的时候是否在 T_2。

转移很简单（省略 u），以 s=0,t=0 举例，剩下三种情况同理：

表示：

• 从 u 跳到 anc_{u,j-1} 的时候是从 0 跳到 0，从 anc_{u,j-1} 跳到 anc_{u,j} 的时候还是从 0 跳到 0。
• 从 u 跳到 anc_{u,j-1} 的时候是从 0 跳到 1，从 anc_{u,j-1} 跳到 anc_{u,j} 的时候是从 1 回到 0。

查询就维护两个状态，当前是在 T_1 还是 T_2，用倍增数组做转移即可。

然而，初始状态怎么设呢？

也就是说，我要求：对于一个对应点 u，从 T_1 的 u_1 跳到 T_2 的 u_2，最少需要多少代价？

从 u_2 走到 u_1 也是同样的代价，我们设其为 c_u。

在这个图中，有三种方式：

可以构造数据让其中的任意一种变为最优。拿最后一个来举例：

显然这就是一种让最后一种方案成为最优的构造。

也就是说，我们可以借助一个点 v，构造路径为 u_1\to v_1\to v_2\to u_2。

想到这里，你不免会接着想——会不会有更复杂的结构呢？比如 u_1\to v_1\to v_2\to x_2\to x_1\to y_1\to y_2\to u_2。

蒟蒻当时就是在这里卡了一下。

答案是否定的。

首先可以想象到，一条最优路径肯定不会重复经过一个点，因为边权都为正。

这个好理解吧，紫色箭头所指那段重复走了，所以我们可以把黑色路径换成绿色那一条。

接下来如果直接证好像有点复杂，我们换个角度看问题。

如果我们想象成，一个带着红绿属性的点在一棵树上走呢？把原来的换树，变成换颜色。

由于不能重复走一个点，所以我们把所有走过的点染上色，当时是红色就把点染上红色，是绿色就染上绿色。如果在一个点切换颜色，那两种色都染上。

由刚刚发现的性质，我是绿色的时候就不能走染过绿色的点了，红色的时候不能走红色点。

我们的要求是，从红 u 出发，回到绿 u。

直觉告诉我们，考虑第一次换颜色的地方，设为 v。

如果我们到达 v 之后不回头，再往下走会怎么样？

先不管下面发生了什么，我最后肯定要穿过 v 再回到 u。

而此时 v 两个颜色都有，无论你当前是红色还是绿色，都不能碰它，因为刚刚说了不能碰相同颜色的点。

也就是说我蓝色那一步根本走不了。

所以我们得出一个结论：你在一个点换了颜色，一定要立马掉头往回。

所以最终解会形成下面的形态：

欸这个时候你发现不对劲了：我 s_2 在返回的时候，u 不是已经染过红色了吗？所以走 s_2 是不合法的。

所以只能选择一个 s_1 往返一次。如果 u\to v\to u 已经到达 u 了，再次离开，就会在红色状态下经过红 u。

得到结论：最优解路线一定是 u_1\to v_1\to v_2\to u_2。若 v=u，则直接在 u 换色。

如何维护这个东西呢？

我们可以先把子树内的最优解算出来，然后再进行一次 DFS，用父节点更新子节点，得到非子树内的信息。有点类似换根 DP。

具体一点，设 w_u 为 u 到父亲连边的权值，子树内结果为 sub_u。

我们第一次 DFS 先求出 sub_u：

第二次 DFS 用父亲 f 更新 u：

所以这道题就做完了。

代码

细节不多，我喜欢 qwq。

这里用 u 表示 u_1，n + u 表示 u_2。

转移看似复杂，其实简单清晰。

static constexpr int MAXN = (int)(6e5) + 10;
static constexpr int logN = 19, LogN = 20;

int n, q; int d[MAXN], w[MAXN];
vector<int> e[MAXN];
struct Edge {
    int u, v, w1, w2;
};
Edge es[MAXN];
int sub[MAXN], c[MAXN];
int anc[MAXN][LogN];
int fa[MAXN], dep[MAXN];
int sum[MAXN][LogN][2][2];

void dfs_pre(int u, int f) {
    fa[u] = f, dep[u] = dep[f] + 1;
    for (int v : e[u]) {
        if (v == f) continue;
        dfs_pre(v, u);
    }
}
void dfs_sub(int u) {
    sub[u] = d[u];
    for (int v : e[u]) {
        if (v == fa[u]) continue;
        dfs_sub(v);
        cmin(sub[u], sub[v] + w[v] + w[n + v]);
    }
}
void dfs_anc(int u) {
    c[u] = sub[u];
    if (u > 1) cmin(c[u], c[fa[u]] + w[u] + w[n + u]);
    for (int v : e[u]) {
        if (v == fa[u]) continue;
        dfs_anc(v);
    }
}

void trans(const auto &a, const auto &b, auto &c) {
    c[0][0] = min(a[0][0] + b[0][0], a[0][1] + b[1][0]);
    c[1][1] = min(a[1][1] + b[1][1], a[1][0] + b[0][1]);
    c[0][1] = min(a[0][0] + b[0][1], a[0][1] + b[1][1]);
    c[1][0] = min(a[1][1] + b[1][0], a[1][0] + b[0][0]);
}

signed main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> d[i];
    for (int i = 1, u, v, w1, w2; i < n; i++) {
        cin >> u >> v >> w1 >> w2;
        es[i] = (Edge){u, v, w1, w2};
        e[u].eb(v), e[v].eb(u);
    }
    dfs_pre(1, 0);
    for (int i = 2; i <= n; i++)
        fa[n + i] = n + fa[i];
    for (int i = 1; i < n; i++) {
        Edge it = es[i];
        int son = (fa[it.u] == it.v ? it.u : it.v);
        w[son] = it.w1, w[n + son] = it.w2;
    }
    dfs_sub(1), dfs_anc(1);
    for (int i = 1; i <= n; i++) {
        anc[i][0] = fa[i];
        sum[i][0][0][0] = min(c[i] + w[n + i] + c[fa[i]], w[i]);
        sum[i][0][1][1] = min(c[i] + w[i] + c[fa[i]], w[n + i]);
        sum[i][0][0][1] = min(c[i] + w[n + i], w[i] + c[fa[i]]);
        sum[i][0][1][0] = min(c[i] + w[i], w[n + i] + c[fa[i]]);
    }
    for (int j = 1; j <= logN; j++) {
        for (int i = 1; i <= n; i++) {
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
            trans(sum[i][j - 1], sum[anc[i][j - 1]][j - 1], sum[i][j]);
        }
    }

    cin >> q;
    auto glca = [&](int u, int v) -> int {
        if (dep[u] < dep[v]) std::swap(u, v);
        for (int i = logN; i >= 0; i--)
            if (dep[anc[u][i]] >= dep[v]) u = anc[u][i];
        if (u == v) return u;
        for (int i = logN; i >= 0; i--)
            if (anc[u][i] != anc[v][i])
                u = anc[u][i], v = anc[v][i];
        return fa[u];
    };
    auto gres = [&](auto &s, int u, int lca) -> void {
        for (int i = logN; i >= 0; i--) {
            if (dep[anc[u][i]] < dep[lca]) continue;
            int s0 = s[0], s1 = s[1];
            s[0] = min(s0 + sum[u][i][0][0], s1 + sum[u][i][1][0]);
            s[1] = min(s1 + sum[u][i][1][1], s0 + sum[u][i][0][1]);
            u = anc[u][i];
        }
    };

    for (int u, v, x, y; q > 0; q--) {
        cin >> x >> y, u = (x + 1) / 2, v = (y + 1) / 2;
        x = (x % 2 == 0 ? n + u : u), y = (y % 2 == 0 ? n + v : v);
        int lca = glca(u, v);
        static int sx[2], sy[2];
        sx[x > n] = 0, sx[(x > n) ^ 1] = c[u];
        sy[y > n] = 0, sy[(y > n) ^ 1] = c[v];
        gres(sx, u, lca), gres(sy, v, lca);
        cout << min(sx[0] + sy[0], sx[1] + sy[1]) << '\n';
    }

    return 0;
}