大意
给定一棵树，求出一条路径
p
p
p，使得其的权值
S
≤
k
≤
E
S\leq k\leq E
S≤k≤E
思路
正解点分治
d
f
s
dfs
dfs代码(70)
#include<cstdio>
#include<algorithm>
#define ri register int
using namespace std
;int n
,S
,E
,l
[100001],x
,y
,w
,tot
,minn
=2147483647;
struct node
{int next
,to
,w
;}e
[200001];
inline void add(ri u
,ri v
,ri w
){e
[++tot
]=(node
){l
[u
],v
,w
};l
[u
]=tot
;return;}
bool vis
[100001];
inline void dfs(ri x
,ri now
,ri from
)
{
if(now
>=S
)
{
if(now
>=minn
) return;
minn
=now
;
}
if(now
>E
) return;
for(ri i
=l
[x
];i
;i
=e
[i
].next
)
{
int y
=e
[i
].to
,w
=e
[i
].w
;
if(y
!=from
) dfs(y
,now
+w
,x
);
}
return;
}
signed main()
{
scanf("%d%d%d",&n
,&S
,&E
);
for(ri i
=1;i
<n
;i
++)
{
scanf("%d%d%d",&x
,&y
,&w
);
if(w
<=E
)
{
add(x
,y
,w
);add(y
,x
,w
);
if(w
>=S
&&w
<minn
) minn
=w
;
}
}
if(minn
<2147483647) return printf("%d",minn
)&0;
for(ri i
=1;i
<=n
;i
++) dfs(i
,0,-1);
if(minn
<2147483647) return printf("%d",minn
)&0;
puts("-1");
}
点分治代码
#include<cstdio>
#include<algorithm>
#define ri register int
using namespace std
;int n
,S
,E
,l
[100010],x
,y
,w
,tot
,Ans
=2147483647;
struct node
{int next
,to
,w
;}e
[200020];
struct Node
{int len
,father
;}s
[100010];
int sz
[100010],rt
,f
[100010]={1<<27},d
[100010],t
,fs
[100010],nt
[100010],ns
;
bool vis
[100010];
inline void add(ri u
,ri v
,ri w
){e
[++tot
]=(node
){l
[u
],v
,w
};l
[u
]=tot
;return;}
inline void gmin(ri
&x
,ri y
){if(x
>y
)x
=y
;return;}
inline void gmax(ri
&x
,ri y
){if(x
<y
)x
=y
;return;}
inline bool cmp(Node x
,Node y
){return x
.len
<y
.len
;}
inline void groot(ri x
,ri fa
)
{
sz
[x
]=1;f
[x
]=0;
for(ri i
=l
[x
];i
;i
=e
[i
].next
)
{
int y
=e
[i
].to
;
if(y
==fa
||vis
[y
]) continue;
groot(y
,x
);
sz
[x
]+=sz
[y
];gmax(f
[x
],sz
[y
]);
}
gmax(f
[x
],ns
-sz
[x
]);
if(f
[x
]<f
[rt
]) rt
=x
;
return;
}
inline void gparent(ri x
,ri fa
)
{
s
[++t
]=(Node
){d
[x
],fs
[x
]};
for(ri i
=l
[x
];i
;i
=e
[i
].next
)
{
int y
=e
[i
].to
,w
=e
[i
].w
;
if(y
==fa
||vis
[y
]) continue;
if(fa
)fs
[y
]=fs
[x
];d
[y
]=d
[x
]+w
;
gparent(y
,x
);
}
return;
}
inline void gcal(ri x
)
{
d
[x
]=0;t
=0;fs
[x
]=x
;
for(ri i
=l
[x
];i
;i
=e
[i
].next
) fs
[e
[i
].to
]=e
[i
].to
;
gparent(x
,0);sort(s
+1,s
+1+t
,cmp
);nt
[t
]=t
+1;
for(ri i
=t
-1;i
;i
--) nt
[i
]=s
[i
].father
==s
[i
+1].father
?nt
[i
+1]:i
+1;
for(ri l
=1,r
=t
;l
<r
;++l
)
{
for(;l
<r
&&s
[r
-1].len
+s
[l
].len
>=S
;r
--);
if(s
[l
].father
==s
[r
].father
) r
=nt
[r
];
if(r
<=t
&&s
[l
].len
+s
[r
].len
>=S
) gmin(Ans
,s
[l
].len
+s
[r
].len
);
}
return;
}
inline void dfs(ri x
)
{
gcal(x
);vis
[x
]=true;
for(ri i
=l
[x
];i
;i
=e
[i
].next
)
{
int y
=e
[i
].to
;
if(!vis
[y
])
{
rt
=0;ns
=sz
[x
];
groot(y
,x
);dfs(rt
);
}
}
return;
}
signed main()
{
scanf("%d%d%d",&n
,&S
,&E
);
for(ri i
=1;i
<n
;i
++)
{
scanf("%d%d%d",&x
,&y
,&w
);
add(x
,y
,w
);add(y
,x
,w
);
}
ns
=n
;groot(1,0);
dfs(rt
);
if(Ans
>E
) puts("-1");else printf("%d",Ans
);
}
转载请注明原文地址: https://www.6miu.com/read-5029259.html
