题解：P9305 「DTOI-5」校门外的枯树

· · 题解

额，事实上我自己做出来的部分只有 41 分，是某大佬指点迷津才 AC 的。

设 $M_i$ 表示以 $i$ 为根节点的字数的重量。 ## $k=1

这部分相当好拿分。先预处理 M_i。

链 1\sim i 的左边部分的重量和右边部分的重量是容易处理的。这样 k=1 就做出来了啦。答案就是重量差的最小值。贴代码：

#include <bits/stdc++.h>
#define rty printf("Yes\n");
#define RTY printf("YES\n");
#define rtn printf("No\n");
#define RTN printf("NO\n");
#define rep(v,b,e) for(int v=b;v<=e;v++)
#define repq(v,b,e) for(int v=b;v<e;v++)
#define rrep(v,e,b) for(int v=b;v>=e;v--)
#define rrepq(v,e,b) for(int v=b;v>e;v--)
#define stg string
#define vct vector
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int k;
const int N = 1E5 + 5;
vct<pair<int ,int> > E[N];
bool yz[N];
int m[N], lef[N], rig[N];

void dfs(int u, int fa) {
    int sum = 0;    
    int tmpsum = 0;
    for (auto tmp : E[u]) {
        int v = tmp.first, w = tmp.second;
        if (v == fa) continue;
        sum += w + m[v];
    }
    for (auto tmp : E[u]) {
        int v = tmp.first, w = tmp.second;
        if (v == fa) continue;
        yz[u] = 1;
        int p0 = tmpsum, p1 = sum - tmpsum - m[v] - w;
        lef[v] = lef[u] + p0, rig[v] = rig[u] + p1;
        tmpsum += m[v] + w;
        dfs(v, u);
    }
}

void dfs_firs(int u, int fa) {
    for (auto tmp : E[u]) {
        int v = tmp.first, w = tmp.second;
        if (v == fa) continue;
        dfs_firs(v, u);
    }
    for (auto tmp : E[u]) {
        int v = tmp.first, w = tmp.second;
        if (v == fa) continue;
        m[u] = m[u] + m[v] + w;
    }
}

void solve() {
    memset(yz, 0, sizeof yz);
    int n;
    cin >> n;
    rep(i, 1, n) {
        E[i].clear();
        m[i] = 0;
    }
    rep(i, 1, n) {
        int x;
        cin >> x;
        rep(j, 1, x) {
            int v, w;
            cin >> v >> w;
            E[i].push_back({v, w});
        }
    }
    dfs_firs(1, 0);
    dfs(1, 0);
    if (k == 1) {
        int ans = 2e9;
        rep(i ,1, n) {
            if (!yz[i])
                ans = min(ans, abs(lef[i] - rig[i]));
        }
        cout << ans << '\n';
    } 
}

main() {
    int t; cin >> t >> k; while (t--) solve();

    return 0;
}

k=2

其实 k=1 做完了 k=2 也很好想，鄙人大脑完全不发育竟然没想到。

取所有的叶子结点，注意到因为同一层的结点 M_i 单调递增。可以二分叶子结点，完成 k=2 的部分。

接下来我们换一种处理方式：

则对于以 i 为根节点的树中，链 i\sim j 的重量就是 S_j-S_i，链 i\sim j 的重量与其左侧部分的重量之和就是 L_j-L_i。

加个二分优化，就做完了。

代码：

#include <bits/stdc++.h>
#define rty printf("Yes\n");
#define RTY printf("YES\n");
#define rtn printf("No\n");
#define RTN printf("NO\n");
#define rep(v,b,e) for(int v=b;v<=e;v++)
#define repq(v,b,e) for(int v=b;v<e;v++)
#define rrep(v,e,b) for(int v=b;v>=e;v--)
#define rrepq(v,e,b) for(int v=b;v>e;v--)
#define stg string
#define vct vector
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int k;
const int N = 1E5 + 5;
vct<pair<int ,int> > E[N];
int m[N], lef[N], dfn_mx[N], dfn_mn[N], cnt, dfn_belonged[N], chain_sum[N];

void dfs_firs(int u) {
    dfn_mn[u] = cnt;
    for (auto tmp : E[u]) {
        int v = tmp.first, w = tmp.second;
        chain_sum[v] = chain_sum[u] + w;
        dfs_firs(v);
        m[u] = m[u] + m[v] + w;
    }
    if (!E[u].size()) {
        ++cnt;
        dfn_belonged[cnt] = u;
    }
    dfn_mx[u] = cnt;
}

void dfs_seco(int u) {
    int sum = 0;
    for (auto tmp : E[u]) {
        int v = tmp.first, w = tmp.second;
        lef[v] = lef[u] + sum + w;
        dfs_seco(v);
        sum += m[v] + w;
    }
}

int query(int from, int to) {
    int wei_chain = chain_sum[to] - chain_sum[from];
    int left = lef[to] - lef[from] - wei_chain;
    return left - (m[from] - left - wei_chain);
}

void solve() {
    memset(dfn_belonged, 0, sizeof dfn_belonged);
    memset(dfn_mx, 0, sizeof dfn_mx);
    memset(dfn_mn, 0, sizeof dfn_mn);
    memset(lef, 0, sizeof lef);
    memset(m, 0, sizeof m);
    memset(chain_sum, 0, sizeof chain_sum);
    lef[1] = chain_sum[1] = 0;
    cnt = 0;
    int n;
    cin >> n;
    rep(i, 1, n) {
        E[i].clear();
        m[i] = 0;
    }
    rep(i, 1, n) {
        int x;
        cin >> x;
        rep(j, 1, x) {
            int v, w;
            cin >> v >> w;
            E[i].push_back({v, w});
        }
    }
    dfs_firs(1);
    dfs_seco(1);
    // cout << chain_sum[5];
    rep(i, 1, n) {
        if (k == 1 && i != 1) {
            continue;
        }
        int l = dfn_mn[i], r = dfn_mx[i];
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (query(i, dfn_belonged[mid]) >= 0) {
                r = mid;
            } else l = mid;
        }
        cout << min(abs(query(i, dfn_belonged[l])), abs(query(i, dfn_belonged[r]))) << ' ';
    }
    cout << '\n';
}

main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t; cin >> t >> k; while (t--) solve();

    return 0;
}