洛谷 P4149 [IOI2011]Race-树分治(点分治，不容斥版)+读入挂-树上求一条路径，权值和等于 K，且边的数量最小

时间：2023-01-20 21:35:24

P4149 [IOI2011]Race

题目描述

给一棵树，每条边有权。求一条简单路径，权值和等于 KK，且边的数量最小。

输入格式

第一行包含两个整数 n, Kn,K。

接下来 n - 1n−1 行，每行包含三个整数，表示一条无向边的两端和权值。

注意点的编号从 00 开始。

输出格式

输出一个整数，表示最小边数量。

如果不存在这样的路径，输出 -1−1。

输入输出样例

输入 #1复制 
4 3

0 1 1

1 2 2

1 3 4
输出 #1复制 
2

说明/提示

保证 n \leqslant 2 \times 10^5,n⩽2×105, K \leqslant 10^6K⩽106。

这道题目我是在cf161D的基础上进行操作的，在维护距离的时候，顺带维护一下边数就可以。

具体细节代码写了注释，心塞，初始化写挫了，调了两天。。。

学习博客推荐：

点分治&动态点分治小结

点分治详细解析

点分治&&动态点分治学习笔记

【算法学习】点分治的两种写法与常见套路总结

还有一个，没看，关于求重心的

一种基于错误的寻找重心方法的点分治的复杂度分析

代码:

 //点分治

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 #pragma GCC optimize(2)

 //#define FI(n) FastIO::read(n)

 const int inf=0x3f3f3f3f;

 const int maxn=2e5+;

 const int maxm=1e6+;

 int head[maxn<<],tot;

 int root,allnode,n,m,k;

 bool vis[maxn];

 int deep[maxn],dis[maxn],siz[maxn],maxv[maxn];//deep为维护边数，dis为距离

 int minline[maxm],ret[maxn],num[maxn],tmp[maxn];//minline维护对应距离最小的边数，ret保存距离，num保存边数，tmp保存出现过的距离，初始化minline用到

 int ans=inf;

 namespace IO{//读入挂

     char buf[<<],*S,*T;

     inline char gc(){

         if (S==T){

             T=(S=buf)+fread(buf,,<<,stdin);

             if (S==T)return EOF;

         }

         return *S++;

     }

     inline int read(){

         int x; bool f; char c;

         for(f=;(c=gc())<''||c>'';f=c=='-');

         for(x=c^'';(c=gc())>=''&&c<='';x=(x<<)+(x<<)+(c^''));

         return f?-x:x;

     }

     inline long long readll(){

         long long x;bool f;char c;

         for(f=;(c=gc())<''||c>'';f=c=='-');

         for(x=c^'';(c=gc())>=''&&c<='';x=(x<<)+(x<<)+(c^''));

         return f?-x:x;

     }

 }

 using IO::read;

 using IO::readll;

 struct node{

     int to,next,val;

 }edge[maxn<<];

 void add(int u,int v,int w)//前向星存图

 {

     edge[tot].to=v;

     edge[tot].next=head[u];

     edge[tot].val=w;

     head[u]=tot++;

 }

 void init()//初始化

 {

     memset(head,-,sizeof head);

     memset(vis,false,sizeof vis);

     for(int i=;i<=k;i++){//初始化保存最小边数

         minline[i]=inf;

     }

     tot=;

 }

 void get_root(int u,int father)//求重心

 {

     siz[u]=;maxv[u]=;

     for(int i=head[u];~i;i=edge[i].next){

         int v=edge[i].to;

         if(v==father||vis[v]) continue;

         get_root(v,u);

         siz[u]+=siz[v];

         maxv[u]=max(maxv[u],siz[v]);

     }

     maxv[u]=max(maxv[u],allnode-siz[u]);

     if(maxv[u]<maxv[root]) root=u;

 }

 void get_dis(int u,int father)//求距离，维护边数

 {

     if(dis[u]>k) return ;//超过K，剪枝

     ans=min(ans,minline[k-dis[u]]+deep[u]);//更新答案

     ret[++ret[]]=dis[u];num[ret[]]=deep[u];//保存新得到的数据，距离和边数

     for(int i=head[u];~i;i=edge[i].next){

         int v=edge[i].to;

         if(v==father||vis[v]) continue;

         int w=edge[i].val;

         dis[v]=dis[u]+w;//更新距离

         deep[v]=deep[u]+;//更新边数

         get_dis(v,u);

     }

 }

 void cal(int u)

 {

     int cnt=;

     for(int i=head[u];~i;i=edge[i].next){

         int v=edge[i].to;

         int w=edge[i].val;

         if(vis[v]) continue;

         ret[]=;dis[v]=w;deep[v]=;//初始化

         get_dis(v,u);

         for(int j=;j<=ret[];j++){

            tmp[++cnt]=ret[j];//临时保存出现过的距离

            minline[ret[j]]=min(minline[ret[j]],num[j]);//更新距离的最小边数

         }

     }

     for(int i=;i<=cnt;i++){

         minline[tmp[i]]=inf;//初始化

     }

 }

 void solve(int u)

 {

     minline[]=;

     cal(u);

     vis[u]=;

     for(int i=head[u];~i;i=edge[i].next){

         int v=edge[i].to;

         if(vis[v]) continue;

         allnode=siz[v];

         root=;maxv[]=inf;

         get_root(v,u);

         solve(root);

     }

 }

 int main()

 {

     n=read();k=read();

     init();

     for(int i=;i<n;i++){

         int u=read(),v=read(),w=read();

         u++,v++;

         add(u,v,w);

         add(v,u,w);

     }

     root=;allnode=n;maxv[]=inf;

     get_root(,);

     solve(root);

     if(ans==inf) printf("-1\n");

     else printf("%d\n",ans);

     return ;

 }

相关文章