传送门 https://www.luogu.org/problemnew/show/P4149
十分显然的点分治
枚举所有点作为两点的 LCA
开一个桶 $pd$ 判断之前子树内是否出现过此路程
对于每一个子树都把子树到根的所有路程 dis 都考虑匹配
如果 $pd[K-dis]=1$ 那么就说明存在匹配
然鹅题目还要求在合法匹配中选最少经过边数的匹配
那么再开一个数组 $dd$ ,$dd[i]$ 存当路程为 i 时经过的最少边数
dfs 一个子树时开一个栈, 存每个路程 ($st$) 和经过的最少边数($d$)
那么 dfs 完一颗子树后就枚举栈中的所有元素, 如果 $pd[K-st[i]]=1$ 并且 $dd[K-st[i]]+d[st[i]]<ans$, 那么更新 ans
再把 $st$ 和 $d$ 分别合并到 $pd$ 和 $dd$ 里, 最后记得还原 $d$
这种方法如果不点分治会被卡成 $O(n^2)$, 所以点分治一波就好了
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cmath>
- #include<cstring>
- #include<vector>
- using namespace std;
- typedef long long ll;
- inline int read()
- {
- int x=0,f=1; char ch=getchar();
- while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
- while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
- return x*f;
- }
- const int N=1e6+7,M=1e6+7,INF=1e9+7;
- int fir[N],from[N<<1],to[N<<1],val[N<<1],cntt;
- inline void add(int &a,int &b,int &c)
- {
- from[++cntt]=fir[a]; fir[a]=cntt;
- to[cntt]=b; val[cntt]=c;
- }
- int n,K,tot,rt,ans=INF;
- int sz[N],mx[N];
- bool vis[N];
- void find_rt(int x,int fa)
- {
- sz[x]=1; mx[x]=0;
- for(int i=fir[x];i;i=from[i])
- {
- int &v=to[i]; if(vis[v]||v==fa) continue;
- find_rt(v,x); sz[x]+=sz[v];
- mx[x]=max(mx[x],sz[v]);
- }
- mx[x]=max(mx[x],tot-mx[x]);
- if(mx[x]<mx[rt]) rt=x;
- }
- int st[N],Top,d[M];
- bool inst[M];// 判断是否在栈中
- void dfs(int x,int fa,int dis,int dep)//dis 存当前的路程, dep 是深度
- {
- if(dis>K) return;// 如果 dis>K 就不用 dfs 了, 不会对答案产生贡献
- if(!inst[dis]) st[++Top]=dis,d[dis]=dep,inst[dis]=1;// 如果 dis 不在栈就入栈
- else if(d[dis]>dep) d[dis]=dep;// 否则考虑更新 d
- for(int i=fir[x];i;i=from[i])
- {
- int &v=to[i]; if(vis[v]||v==fa) continue;
- dfs(v,x,dis+val[i],dep+1);
- }
- }
- int dd[M],q[N],p;//q 是回收池
- bool pd[M];
- void work(int x)
- {
- p=0; pd[0]=1;
- for(int i=fir[x];i;i=from[i])
- {
- int &v=to[i]; if(vis[v]) continue;
- Top=0; dfs(v,x,val[i],1);
- for(int j=1;j<=Top;j++)// 枚举所有路程尝试更新答案
- if(pd[K-st[j]]&&dd[K-st[j]]+d[st[j]]<ans)
- ans=dd[K-st[j]]+d[st[j]];
- for(int j=1;j<=Top;j++)// 把 st 和 d 分别合进 pd 和 dd
- {
- if(!pd[st[j]])
- pd[st[j]]=1,dd[st[j]]=d[st[j]],q[++p]=st[j];
- else if(dd[st[j]]>d[st[j]]) dd[st[j]]=d[st[j]];
- d[st[j]]=0,inst[st[j]]=0;// 合完记得清空
- }
- }
- for(int i=1;i<=p;i++) pd[q[i]]=0,dd[q[i]]=0;// 最后记得要把 pd 和 dd 全部还原
- }
- void solve(int x)// 点分治
- {
- vis[x]=1; work(x);
- for(int i=fir[x];i;i=from[i])
- {
- int &v=to[i]; if(vis[v]) continue;
- tot=sz[v]; rt=0;
- find_rt(v,0); solve(rt);
- }
- }
- int main()
- {
- //freopen("data.in","r",stdin);
- //freopen("data.out","w",stdout);
- n=read(),K=read();
- int a,b,c;
- for(int i=1;i<n;i++)
- {
- a=read(),b=read(),c=read();
- add(a,b,c); add(b,a,c);
- }
- tot=n; mx[0]=INF;
- find_rt(1,0); solve(rt);
- if(ans==INF) printf("-1");
- else printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2931035.html