[bzoj 2599] [IOI2011]Race

一棵n个点边带权的无根树, 求权值和等于k的路径的最少边数, 或报告无解. (n≤2*10^5, 0≤k≤10^6, 0≤边权≤10^6) 点分治, 维护一个数组e, e[i]=到重心的权值和等于i的最少边数.

重新写了一遍, 时隔多个月终于切掉了, 当初迷之WA, 联系管理员希望获得数据, 人家不鸟我......TAT

当时TLE得很惨, 因为我在每一层递归都memset清空一个100万的数组......

我的点分治实现是这样的:

const int N = 2e5, K = 1e6, inf = 1e8;
typedef pair<int, int> ii;
struct Edge {
    int v, w;
};

vector<Edge> adj[N];
vector<int> seq;
int sz[N], e[K + 1], d[N], len[N];
bool g[N];

ii get_centroid(int u, int p, const int& n)
{
    sz[u] = 1;
    ii c(inf, inf);
    int mx = 0;
    Rep (i, 0, adj[u].size()) {
        int v = adj[u][i].v;
        if (v != p && !g[v]) {
            c = min(c, get_centroid(v, u, n));
            sz[u] += sz[v];
            mx = max(mx, sz[v]);
        }
    }
    mx = max(mx, n-sz[u]);
    return c = min(c, ii(mx, u));
}

void update(int u, int p, int& ans, const int& k)
{
    if (len[u] > k) return;
    seq.push_back(u);
    Rep (i, 0, adj[u].size()) {
        int v = adj[u][i].v, w = adj[u][i].w;
        if (v != p && !g[v]) {
            d[v] = d[u] + 1;
            len[v] = len[u] + w;
            update(v, u, ans, k);
        }
    }
    ans = min(ans, e[k - len[u]] + d[u]);
}

inline void add(int st)
{
    Rep (i, st, seq.size()) {
        int v = seq[i];
        e[len[v]] = min(e[len[v]], d[v]);
    }
}

inline void remove()
{
    Rep (i, 0, seq.size()) {
        int v = seq[i];
		e[len[v]] = inf;
    }
    seq.clear();
}

int solve(int u, int n, const int& k)
{
    int x = get_centroid(u, -1, n).second, ans = inf, st = 0;
    g[x] = true;
    e[0] = 0;
    Rep (i, 0, adj[x].size()) {
        int y = adj[x][i].v;
        if (!g[y]) {
            d[y] = 1;
            len[y] = adj[x][i].w;
            update(y, x, ans, k);
            add(st);
            st = seq.size();
        }
    }
    remove();
    Rep (i, 0, adj[x].size()) {
        int y = adj[x][i].v;
        if (!g[y]) ans = min(ans, solve(y, sz[y] < sz[x] ? sz[y] : n-sz[x], k));
    }
    return ans;
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    Rep (i, 0, n-1) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back((Edge){v, w});
        adj[v].push_back((Edge){u, w});
	}
	fill_n(e, k+1, inf);
	int ans = solve(0, n, k);
	printf("%d\n", ans == inf ? -1 : ans);
    return 0;
}