0%

Project4149_[IOI2011]Race项目报告

摘要:点分治解决树上路径问题

P4149 [IOI2011]Race

题面

题目分析

每次找出一个重心,把树上的路径分为两类,一类是经过这个重心的,一类是不经过这个重心的,我们只考虑经过这个重心的路径,分治的思想就很明显了.

考虑每个重心的更新方式,我们记录一个che[i],表示一条权值和为i的路径的最小长度,记录路径的权值和rem[i],长度di[i],每次尝试用k-rem[i]来匹配,再用di[i]来更新che[i]即可.

代码很好懂.

代码

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
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cstdlib"
#include "cctype"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "vector"
#define lxl long long
#define R register
#define INF 9223372036854775807
#define debug(x) printf("debug:%lld\n",x)
const lxl maxn=200010,maxk=1000010;
lxl n,k,EdgeSize,rt,sum,ans=INF;
lxl maxp[maxn],size[maxn],head[maxn],dis[maxn],val[maxn],che[maxk],rem[maxn],di[maxn],q[maxn];
bool vis[maxn];
struct _Edge
{
lxl to,next,val;
}e[maxn<<1];
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
inline void EdgeAdd(lxl from,lxl to,lxl val)
{
e[EdgeSize].to=to;
e[EdgeSize].next=head[from];
e[EdgeSize].val=val;
head[from]=EdgeSize++;
}
void GetRoot(lxl now,lxl from)
{
size[now]=1,maxp[now]=0;
for(R int i(head[now]);~i;i=e[i].next)
{
if(e[i].to==from||vis[e[i].to])continue;
GetRoot(e[i].to,now);
size[now]+=size[e[i].to];
maxp[now]=std::max(maxp[now],size[e[i].to]);
}
maxp[now]=std::max(maxp[now],sum-size[now]);
if(maxp[now]<maxp[rt])rt=now;
}
void GetDis(lxl now,lxl from)
{
rem[++rem[0]]=val[now],di[rem[0]]=dis[now];
for(R int i(head[now]);~i;i=e[i].next)
{
if(from==e[i].to||vis[e[i].to])continue;
dis[e[i].to]=dis[now]+1,val[e[i].to]=val[now]+e[i].val;
GetDis(e[i].to,now);
}
}
void calc(lxl now)
{
q[0]=0;
for(R int i(head[now]);~i;i=e[i].next)
{
if(vis[e[i].to])continue;
val[e[i].to]=e[i].val,dis[e[i].to]=1,rem[0]=0,di[0]=0;
GetDis(e[i].to,now);
for(R int i(1);i<=rem[0];++i)
{
if(k-rem[i]<0)continue;
if(che[k-rem[i]]<INF)ans=std::min(ans,di[i]+che[k-rem[i]]);
}
for(R int i(1);i<=rem[0];++i)if(rem[i]<=k)che[rem[i]]=std::min(che[rem[i]],di[i]),q[++q[0]]=rem[i];
}
for(R int i(1);i<=q[0];++i)che[q[i]]=INF;
}
void slove(lxl now)
{
vis[now]=true,che[0]=0;
calc(now);
for(R int i(head[now]);~i;i=e[i].next)
{
if(vis[e[i].to])continue;
maxp[rt=0]=INF,sum=size[e[i].to];
GetRoot(e[i].to,0),slove(rt);
}
}
int main(void)
{
// freopen("P4149_7.in","r",stdin);
memset(head,-1,sizeof(head));
n=read(),k=read();
for(R int i(1);i<=k;++i)che[i]=INF;
for(R int i(1),u,v,val;i<n;++i)
{
u=read()+1,v=read()+1,val=read();
EdgeAdd(u,v,val),EdgeAdd(v,u,val);
}
maxp[rt]=sum=n;
GetRoot(1,0);
slove(rt);
if(ans<=n)printf("%lld\n",ans);
else printf("-1\n");
return 0;
}