Rockdu's Blog

题目描述

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

输入输出格式

输入格式：

第一行：两个整数 n,k 。

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

输出格式：

一个整数，表示最小边数量。

如果不存在这样的路径，输出 -1 。

输入输出样例

4 3
0 1 1
1 2 2
1 3 4

2

说明

$n\le 200000,K\le 1000000$ 。

点分治裸题，处理每一棵子树。用一个数组记录当前子树之前的所有子树中深度在K以下的点所能有的最小边数。对每一棵子树先根据前面的数据更新答案，然后再把当前子树中深度在K以下的点统计贡献。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 5, maxk = 1e6 + 5, inf = 0x3f3f3f3f;
struct edge {
    int v, w, next;
}e[maxn << 1];
int tmp[maxk], head[maxn], cnt, n, k, size[maxn], vis[maxn], son[maxn];
int w[maxn], d[maxn], ans = inf;
void adde(const int &u, const int &v, const int &w) {
    e[++cnt] = (edge) {v, w, head[u]};
    head[u] = cnt;
}

void FindG(int u, int p, int tot, int & G) {
    son[u] = 0, size[u] = 1;
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == p || vis[v]) continue;
        FindG(v, u, tot, G);
        size[u] += size[v];
        son[u] = max(son[u], size[v]);
    }
    son[u] = max(son[u], tot - size[u]);
    if(son[G] > son[u]) G = u;
}

void calc(int u, int p) {
    if(w[u] <= k) ans = min(ans, tmp[k - w[u]] + d[u]);
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == p || vis[v]) continue;
        d[v] = d[u] + 1, w[v] = w[u] + e[i].w, calc(v, u);
    }
}

void EditTmp(int u, int p) {
    if(w[u] <= k) tmp[w[u]] = min(tmp[w[u]], d[u]);
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == p || vis[v]) continue;
        EditTmp(v, u); 
    }	
}

void ClearTmp(int u, int p) {
    if(w[u] <= k) tmp[w[u]] = inf;
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == p || vis[v]) continue;
        ClearTmp(v, u); 
    }	
}

int G;
void Solve(int u) {
    int v;u = G, vis[u] = 1, tmp[0] = 0;
    for(register int i = head[u]; i; i = e[i].next) {
        v = e[i].v;
        if(vis[v]) continue;
        w[v] = e[i].w, d[v] = 1;
        calc(v, 0), EditTmp(v, 0);
    }
    for(register int i = head[u]; i; i = e[i].next)
        if(!vis[v = e[i].v]) ClearTmp(v, u);
    for(register int i = head[u]; i; i = e[i].next) 
        if(!vis[v = e[i].v]) G = 0, FindG(v, u, size[v], G), Solve(G);
    
}

int u, v, W;
int main() {
    memset(tmp, inf, sizeof(tmp));
    scanf("%d%d", &n, &k);
    for(register int i = 1; i < n; ++i) 
        scanf("%d%d%d", &u, &v, &W), ++u, ++v, adde(u, v, W), adde(v, u, W);
    son[0] = inf, FindG(1, 0, n, G), Solve(G);
    printf("%d", ans == inf ? -1 : ans);
    return 0;
}