「IOI 2011」Race

发表于 | | 阅读次数:
字数统计: 569 字

Description

题目链接：Luogu 4149

给一棵有 $n$ 个节点的树，每条边有权。求一条简单路径，权值和等于 $k$，且边的数量最小。无解输出 $-1$。

数据范围：$1\le n\le 2\times 10^5$，$1\le k\le 10^6$

Solution

IOI 点分治入门题

为了方便计数，我们采用分别处理每棵子树的方法，而不是容斥（容斥无限 $\text{WA}$ 根本调不出来 QAQ）。

记录 $f_i$ 表示长度为 $i$ 的链包含的最小边数，对于长度大于 $k$ 的链可以直接忽略。

时间复杂度：$O(n\log n)$

Code

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
 
#include <cstdio>
#include <algorithm>

const int N=2e5+5,M=4e5+5,K=1e6+5;
const int INF=1<<30;
int n,k,tot,tp,root,sum,lnk[N],ter[M],nxt[M],val[M],mx[N],sz[N],q[N],f[K],ans;
bool vis[N];
std::pair<int,int> s[N];

void add(int u,int v,int w) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
void getRoot(int u,int fa) {
    sz[u]=1,mx[u]=0;
    for(int i=lnk[u];i;i=nxt[i]) {
        int v=ter[i];
        if(v==fa||vis[v]) continue;
        getRoot(v,u);
        sz[u]+=sz[v];
        mx[u]=std::max(mx[u],sz[v]);
    }
    mx[u]=std::max(mx[u],sum-sz[u]);
    if(mx[root]>mx[u]) root=u;
}
void getDis(int u,int fa,int d,int p) {
    if(d>k) return;
    s[++tp]=std::make_pair(d,p);
    for(int i=lnk[u];i;i=nxt[i]) {
        int v=ter[i];
        if(v==fa||vis[v]) continue;
        getDis(v,u,d+val[i],p+1);
    }
}
void solve(int u) {
    int cnt=0;
    for(int i=lnk[u];i;i=nxt[i]) {
        int v=ter[i];
        if(vis[v]) continue;
        tp=0,getDis(v,u,val[i],1);
        for(int i=1;i<=tp;++i) ans=std::min(ans,s[i].second+f[k-s[i].first]);
        for(int i=1;i<=tp;++i) f[q[++cnt]=s[i].first]=std::min(f[s[i].first],s[i].second);
    }
    for(int i=1;i<=cnt;++i) f[q[i]]=INF;
}
void dfs(int u) {
    vis[u]=1,f[0]=0,solve(u);
    for(int i=lnk[u];i;i=nxt[i]) {
        int v=ter[i];
        if(vis[v]) continue;
        root=0,sum=sz[v],getRoot(v,u),dfs(root);
    }
}
int main() {
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;++i) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w),++u,++v;
        add(u,v,w),add(v,u,w);
    }
    for(int i=0;i<=k;++i) f[i]=INF;
    ans=mx[0]=INF;
    root=0,sum=n,getRoot(1,0),dfs(root);
    printf("%d\n",ans==INF?-1:ans);
    return 0;
}
0%