[bzoj2599][点分治]Race

127 阅读 0 评论 84 点赞

我是靠谱客的博主优雅蜜粉，这篇文章主要介绍[bzoj2599][点分治]Race，现在分享给大家，希望可以做个参考。

Description

给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000

Input

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

Output

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

Sample Input

4 3

0 1 1

1 2 2

1 3 4

Sample Output

2

HINT

2018.1.3新加数据一组，未重测

题解

很明显的点分
设li[i][0]/li[i][1]分别表示到当前根长度为i的路径最短/次短的两条，并强制要求这两条路径来自不同子树。优先考虑最短其次次短
由于每次只会有比上一次少一半的点做出贡献，所以复杂度是 $O(nlog n)$
打个时间戳回收一下数组
然后就可以很愉快地点分啦

复制代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
struct po{int s,fro;}w[210000];int ln;
struct list{int c,fro,tim;}li[1110000][2];int ti,n,m;
//pt divide
struct node{int x,y,c,next;}a[410000];int len,last[210000];
void ins(int x,int y,int c){len++;a[len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}
int f[210000],tot[210000],G,sum;
bool v[210000];
void getrt(int x,int fa)
{
    tot[x]=1;f[x]=0;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y!=fa && !v[y])
        {
            getrt(y,x);
            f[x]=max(f[x],tot[y]);
            tot[x]+=tot[y];
        }
    }
    f[x]=max(f[x],sum-tot[x]);
    if(f[G]>f[x])G=x;
}
void dfs(int x,int fa,int dis,int e,int fro)
{
    if(dis<=m)
    {
        ln++;w[ln].s=dis;w[ln].fro=fro;
        if(e<li[dis][0].c || li[dis][0].tim!=ti)
        {
            list tmp=li[dis][0];
            li[dis][0].c=e;li[dis][0].fro=fro;li[dis][0].tim=ti;
            if(tmp.tim==ti && tmp.fro!=fro)
            {
                if(li[dis][1].c>=tmp.c || li[dis][1].tim!=ti)li[dis][1]=tmp;
            }
        }
        else if((e<li[dis][1].c|| li[dis][1].tim!=ti) && li[dis][0].fro!=fro)li[dis][1].c=e,li[dis][1].fro=fro,li[dis][1].tim=ti;
    }
    else return ;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y!=fa && !v[y])dfs(y,x,dis+a[k].c,e+1,fro);
    }
}
int ans;
void getans()
{
    int ss=999999999;
    for(int j=1;j<=ln;j++)
    {
        int i=w[j].s;
        if(li[i][0].tim==ti && li[m-i][0].tim==ti)
        {
            int e=999999999;
            if(li[i][0].fro!=li[m-i][0].fro)e=li[i][0].c+li[m-i][0].c;
            if(li[i][0].fro!=li[m-i][1].fro && li[m-i][1].tim==ti)e=min(e,li[i][0].c+li[m-i][1].c);
            if(li[i][1].fro!=li[m-i][0].fro && li[i][1].tim==ti)e=min(e,li[i][1].c+li[m-i][0].c);
            if(li[i][1].fro!=li[m-i][1].fro && li[m-i][1].tim==ti && li[i][1].tim==ti)e=min(e,li[i][1].c+li[m-i][1].c);
            ss=min(ss,e);
        }
    }
    if(li[m][0].tim==ti)ans=min(ans,li[m][0].c);
    ans=min(ans,ss);
}
void sol(int x)
{
    v[x]=true;ti++;ln=0;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(!v[y])dfs(y,x,a[k].c,1,y);
    }
    getans();
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(!v[y])
        {
            G=0;sum=tot[y];
            getrt(y,x);
            sol(G);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    len=0;memset(last,0,sizeof(last));
    for(int i=1;i<n;i++)
    {
        int x,y,c;scanf("%d%d%d",&x,&y,&c);
        x++;y++;ins(x,y,c);ins(y,x,c);
    }
    memset(v,false,sizeof(v));
    f[0]=999999999;G=0;sum=n;
    getrt(1,0);
    ans=999999999;sol(G);
    if(ans!=999999999)printf("%dn",ans);
    else printf("-1n");
    return 0;
}

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
100
101
102
103
104
105
106
107
108
109
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
struct po{int s,fro;}w[210000];int ln;
struct list{int c,fro,tim;}li[1110000][2];int ti,n,m;
//pt divide
struct node{int x,y,c,next;}a[410000];int len,last[210000];
void ins(int x,int y,int c){len++;a[len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}
int f[210000],tot[210000],G,sum;
bool v[210000];
void getrt(int x,int fa)
{
    tot[x]=1;f[x]=0;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y!=fa && !v[y])
        {
            getrt(y,x);
            f[x]=max(f[x],tot[y]);
            tot[x]+=tot[y];
        }
    }
    f[x]=max(f[x],sum-tot[x]);
    if(f[G]>f[x])G=x;
}
void dfs(int x,int fa,int dis,int e,int fro)
{
    if(dis<=m)
    {
        ln++;w[ln].s=dis;w[ln].fro=fro;
        if(e<li[dis][0].c || li[dis][0].tim!=ti)
        {
            list tmp=li[dis][0];
            li[dis][0].c=e;li[dis][0].fro=fro;li[dis][0].tim=ti;
            if(tmp.tim==ti && tmp.fro!=fro)
            {
                if(li[dis][1].c>=tmp.c || li[dis][1].tim!=ti)li[dis][1]=tmp;
            }
        }
        else if((e<li[dis][1].c|| li[dis][1].tim!=ti) && li[dis][0].fro!=fro)li[dis][1].c=e,li[dis][1].fro=fro,li[dis][1].tim=ti;
    }
    else return ;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y!=fa && !v[y])dfs(y,x,dis+a[k].c,e+1,fro);
    }
}
int ans;
void getans()
{
    int ss=999999999;
    for(int j=1;j<=ln;j++)
    {
        int i=w[j].s;
        if(li[i][0].tim==ti && li[m-i][0].tim==ti)
        {
            int e=999999999;
            if(li[i][0].fro!=li[m-i][0].fro)e=li[i][0].c+li[m-i][0].c;
            if(li[i][0].fro!=li[m-i][1].fro && li[m-i][1].tim==ti)e=min(e,li[i][0].c+li[m-i][1].c);
            if(li[i][1].fro!=li[m-i][0].fro && li[i][1].tim==ti)e=min(e,li[i][1].c+li[m-i][0].c);
            if(li[i][1].fro!=li[m-i][1].fro && li[m-i][1].tim==ti && li[i][1].tim==ti)e=min(e,li[i][1].c+li[m-i][1].c);
            ss=min(ss,e);
        }
    }
    if(li[m][0].tim==ti)ans=min(ans,li[m][0].c);
    ans=min(ans,ss);
}
void sol(int x)
{
    v[x]=true;ti++;ln=0;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(!v[y])dfs(y,x,a[k].c,1,y);
    }
    getans();
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(!v[y])
        {
            G=0;sum=tot[y];
            getrt(y,x);
            sol(G);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    len=0;memset(last,0,sizeof(last));
    for(int i=1;i<n;i++)
    {
        int x,y,c;scanf("%d%d%d",&x,&y,&c);
        x++;y++;ins(x,y,c);ins(y,x,c);
    }
    memset(v,false,sizeof(v));
    f[0]=999999999;G=0;sum=n;
    getrt(1,0);
    ans=999999999;sol(G);
    if(ans!=999999999)printf("%dn",ans);
    else printf("-1n");
    return 0;
}