「Bzoj 2559」「IOI2011」Race (点分治)

发表于 | 分类于 | | + s

BZOJ 2559
题意：给一棵树，每条边有权。求一条简单路径，权值和等于 $K$，且边的数量最小。

点分治模板题，但是这里维护的是不可加信息，不能用容斥的方法，我们求每个点的值的时候按一定顺序遍历他的儿子，然后将前面的存起来供后面的合并(类似树直径DP)，然后就不用考虑容斥了，都是可行的合并。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 200000 + 5, INF = 0x3f3f3f3f;

    struct edge {
        int v, w, nxt;
    } ed[MAXN * 2];

    int n, k, en, hd[MAXN];
    int wt[MAXN], siz[MAXN], Tsz, rt;
    int vis[MAXN];
    int ans;
    int tot, dis[MAXN], bs[MAXN];

    void ins(int u, int v, int w) {ed[++en] = (edge){v, w, hd[u]}, hd[u] = en;}

    void getRt(int u, int fa) { // 找 u 子树的重心 
        siz[u] = 1, wt[u] = 0;
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa && !vis[e.v]) getRt(e.v, u), siz[u] += siz[e.v], wt[u] = max(wt[u], siz[e.v]);
        }
        wt[u] = max(wt[u], Tsz - siz[u]);
        if(wt[rt] > wt[u]) rt = u;
    }
    void getD(int u, int fa, int D, int b) {
        if (D > k) return ;
        dis[++tot] = D, bs[tot] = b;
        for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa && !vis[e.v]) getD(e.v, u, D + e.w, b + 1);
        }
    }
    int tax[1000000 + 5];
    void calc(int u) {
        tot = 0, tax[0] = 0;
        for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (!vis[e.v]) {
                int whw = tot;
                getD(e.v, u, e.w, 1);
                for (int j = whw + 1; j <= tot; ++j) ans = min(ans, tax[k - dis[j]] + bs[j]);
                for (int j = whw + 1; j <= tot; ++j) tax[dis[j]] = min(tax[dis[j]], bs[j]);
            }
        }
        for (int i = 1; i <= tot; ++i) tax[dis[i]] = INF;
    }
    void dfs(int u) {
        vis[u] = 1;
        calc(u);
        for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (!vis[e.v]) {
                rt = 0, Tsz = siz[e.v], wt[0] = INF, getRt(e.v, 0);
                dfs(rt); // rt
            }
        }
    }

    void clean() {
        en = -1, ms(hd, -1);
        ms(wt, 0), ms(siz, 0), ms(vis, 0);
        ms(tax, 0x3f), ans = INF;
    }
    int solve() {

        clean();
        cin >> n >> k;
        if (k == 0) return printf("0\n"), 0;
        for (int x, y, w, i = 1; i < n; ++i) {
            scanf("%d%d%d", &x, &y, &w);
            ++x, ++y;
            ins(x, y, w), ins(y, x, w);
        }
        rt = 0, Tsz = n, wt[0] = INF, getRt(1, 0);
        dfs(rt);

        if (ans >= n) printf("-1\n"); else printf("%d\n", ans);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
5 3
0 1 1
1 3 1
0 2 1
2 4 5
*/
------ 本文结束 ------