黑暗爆炸 2599. Race

发表于 分类于

链接

https://darkbzoj.tk/problem/2599

题意

给一棵 $N$ $(N\le 2e5)$ 个节点的树,每条边有权.求一条简单路径,权值和等于 $K$ $(K\le 1e6)$,且边的数量最小。

思路

点分治

计算时将按照节点属于当前根的哪个儿子排序，用一个数组 $t$ 记录到当前根的边权和相同的最短边数。

枚举子树节点，遇到属于当前根的儿子节点与前面不同时，先将前面一段更新到数组，这样可以过滤掉不合法的组合，不用容斥处理。

假设当前枚举到节点 $a$，更新答案 $res=\min(dep[a]+t[k-dist[a]])$，按照上述处理可以保证 $t$ 数组内的信息与当前节点的组合一定是合法的。

计算完后，再次枚举子树节点，将 $t$ 初始化。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
// head
const int N=2e5+5;
int n,k,sz[N],mx[N],dist[N],dep[N],a[N],b[N],mn[N*5],cnt,rt,res=0x3f3f3f3f;
bool st[N];
VPII g[N];
void get_rt(int u,int fa,int sum) {
    sz[u]=1;
    mx[u]=0;
    for(auto x:g[u]) {
        int v=x.FI;
        if(v==fa||st[v]) continue;
        get_rt(v,u,sum);
        sz[u]+=sz[v];
        mx[u]=max(mx[u],sz[v]);
    }
    mx[u]=max(mx[u],sum-sz[u]);
    if(mx[u]<mx[rt]) rt=u;
}
void dfs(int u,int fa,int t) {
    for(auto x:g[u]) {
        int v=x.FI,w=x.SE;
        if(v==fa||st[v]||dist[u]+w>k) continue;
        dist[v]=dist[u]+w;
        dep[v]=dep[u]+1;
        a[++cnt]=v;
        b[v]=t;
        dfs(v,u,t);
    }
}
bool cmp(int x,int y) {
    return b[x]<b[y];
}
void calc(int u) {
    dist[u]=dep[u]=0;
    a[cnt=1]=u;
    b[u]=0;
    for(auto x:g[u]) {
        int v=x.FI,w=x.SE;
        if(st[v]||w>k) continue;
        a[++cnt]=v;
        b[v]=v;
        dist[v]=dist[u]+w;
        dep[v]=dep[u]+1;
        dfs(v,u,v);
    }
    sort(a+1,a+1+cnt,cmp);
    int l=1,r=0;
    for(int i=1;i<=cnt;i++) {
        if(b[a[i]]==b[a[l]]) ++r;
        else {
            for(int j=l;j<=r;j++) mn[dist[a[j]]]=min(mn[dist[a[j]]],dep[a[j]]);
            l=r=i;
        }
        res=min(res,dep[a[i]]+mn[k-dist[a[i]]]);
    }
    for(int i=1;i<=cnt;i++) mn[dist[a[i]]]=0x3f3f3f3f;
}
void divide(int u) {
    mx[rt=0]=INT_MAX;
    get_rt(u,0,sz[u]);
    st[u=rt]=true;
    calc(u);
    for(auto x:g[u]) {
        int v=x.FI;
        if(st[v]) continue;
        divide(v);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    for(int i=1;i<n;i++) {
        int u,v,w;cin>>u>>v>>w;
        ++u,++v;
        g[u].EB(v,w);
        g[v].EB(u,w);
    }
    memset(mn,0x3f,sizeof mn);
    sz[1]=n;divide(1);
    cout<<(res==0x3f3f3f3f?-1:res)<<'\n';
    return 0;
}