BZOJ 2599: [IOI2011]Race( 点分治 )

时间:2023-12-24 12:29:49

BZOJ 2599: [IOI2011]Race( 点分治 )

数据范围是N:20w, K100w. 点分治, 我们只需考虑经过当前树根的方案. K最大只有100w, 直接开个数组CNT[x]表示与当前树根距离为x的最少边数, 然后就可以对根的子树依次dfs并更新CNT数组和答案. 复杂度是O(NlogN)

------------------------------------------------------------------------------------------

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 200009;
const int maxk = 1000009;
const int INF = 0x3F3F3F3F;
inline int read() {
    int ret = 0;
    char c = getchar();
    for(; !isdigit(c); c = getchar());
    for(; isdigit(c); c = getchar())
        ret = ret * 10 + c - '0';
    return ret;
}
int N, K, size[maxn], Rt, best, n, CNT[maxk], _n, ANS = INF;
pii T[maxn];
bool vis[maxn];
struct edge {
    int to, w;
    edge* next;
} E[maxn << 1], *pt = E, *head[maxn];
inline void add(int u, int v, int w) {
    pt->to = v; pt->w = w; pt->next = head[u]; head[u] = pt++;
}
inline void addedge(int u, int v, int w) {
    add(u, v, w); add(v, u, w);
}
void dfs(int x, int fa = -1) {
    size[x] = 1;
    int mx = 0;
    for(edge* e = head[x]; e; e = e->next) if(e->to != fa && !vis[e->to]) {
        dfs(e->to, x);
        size[x] += size[e->to];
        mx = max(mx, size[e->to]);
    }
    if((mx = max(mx, n - size[x])) < best) Rt = x, best = mx;
}
void DFS(int x, int dist, int cnt, int fa) {
    if(dist > K) return;
    ANS = min(ANS, cnt + CNT[K - dist]);
    T[_n++] = make_pair(dist, cnt++);
    for(edge* e = head[x]; e; e = e->next) if(e->to != fa && !vis[e->to])
        DFS(e->to, dist + e->w, cnt, x);
}
void solve(int x) {
    best = INF; dfs(x); x = Rt;
    int p = _n = 0;
    for(edge* e = head[x]; e; e = e->next) if(!vis[e->to]) {
        DFS(e->to, e->w, 1, x);
        for(int i = p; i < _n; i++) 
            CNT[T[i].first] = min(CNT[T[i].first], T[i].second);
        p = _n;
    }
    for(int i = 0; i < _n; i++) CNT[T[i].first] = INF; CNT[0] = 0;
    vis[x] = true;
    for(edge* e = head[x]; e; e = e->next) if(!vis[e->to]) {
        n = size[e->to];
        solve(e->to);
    }
}
void init() {
    N = read(); K = read();
    for(int i = 1; i < N; i++) {
        int u = read(), v = read(), w = read();
        addedge(u, v, w);
    }
}
int main() {
    init();
    n = N;
    memset(CNT, INF, sizeof CNT); CNT[0] = 0;
    solve(0);
    printf("%d\n", ANS != INF ? ANS : -1);
    return 0;
}

------------------------------------------------------------------------------------------

2599: [IOI2011]Race

Time Limit: 50 Sec  Memory Limit: 128 MB
Submit: 1806  Solved: 538
[Submit][Status][Discuss]

Description

给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.

Input

第一行 两个整数 n, k
第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)

Output

一个整数 表示最小边数量 如果不存在这样的路径 输出-1

Sample Input

4 3
0 1 1
1 2 2
1 3 4

Sample Output

2

HINT

Source