题解 P2680 【运输计划】
___new2zy___ · · 题解
题解 P2680 【运输计划】
题目传送门：
https://www.luogu.org/problemnew/show/P2680
话说。。。这题这么毒瘤真的有人能在考场上1A么
敬请观看：爆蛋的NOIp（逃
(以上都是废话,下面才是正文)
主要考察:最近公共祖先(LCA)+树上差分+二分答案
==========================================================
题目简要概括(人性翻译)
仔细读题后,我们发现题面可以简要概括成:
给你一个n个点的树,对于n-1条边各有边权,
给出一些点对(x,y),同时定义dis(x,y)表示x,y两点间的树上距离,
现允许你将一条边的权值变为0,请你最小化最大的dis值如果你大概理解了大意,就可以看下面了
==========================================================
思路&&算法分析:
先来讲一讲错误的想法VS正解
(至少让我把自己的伪正解讲一下= =)
做法一(错误方法):树剖+LCA+贪心+树上差分+线段树
(这里是错误的解题方法,但是我也要讲一下,避免同学们犯和我一样的错误)
(可能没人跟我一样傻吧...xjb贪心)
上来二话没说直接打了个树剖LCA+贪心+树上差分+线段树
以为自己要AKrank 1了,开心的走了
(结果模拟赛成绩出来,直接爆蛋...)
伪正解
仔细思索发现,如果一条边被经过的次数越多,那么这条边越有可能是那个被删掉的边,因为它对于多数的dis值都有影响
那么有一种贪心的想法:不妨找出这条边,把它删除之后统计剩下点对中dis值减去这条边的边权之后最大值即为最小化的dis值
但是这样又很难实现...比如像我,为了统计每一个点对的dis值,开了一发线段树....
(其实只是为了统计树上路径的边权之和)
用线段树维护区间的边权和...总之就是各种乱搞
代码长度陡然上升为187行...最后还是不对
其实仔细思考一下会发现这个贪心是显然不对的
(但是我却没看出来)
试想:我们有一颗很大的树,有一条很长的询问路径,但是它不经过我们选择的那条边,那么我们就没有达到让最大的dis值最小的目标,所以算法的选择是有误的
(但是这样我还得了35分)(逃
错误解法就不发代码了吧(怕丢人+捂脸)
还是来讲标算吧
做法二(正确做法):LCA+二分答案+树上差分
既然是正解,来讲一下如何考虑
为了使得最长的路径最短,我们自然地想到二分答案
对于答案的单调性,也是显然的
因为如果我们能在t1时间内走完一个路径,那么显然对于一个时间t2>t1,总是能够走完的
那么证明本题答案具有单调性
那么如何将二分答案转移到树上呢?
不妨考虑二分最终所有请求的最大树上距离,最后只需判断是否能够通过删掉一条边的边权,最终能否达到这个最大距离即可
这样就将一个求解问题转化为了判定问题
而根据计算机理论,判定往往比求解更加迅速,而且更加简便
那么正解就呼之欲出了
要求路径的最大值最小，可以二分这个最小值
每次判断树上是否存在一条边，能被比当前二分值大的路径都覆盖
对于一段树上路径的距离,可以树上前缀和处理,
我们定义dis[node]表示node节点到根节点的路径上的边权之和
那么显然只需要dfs一遍就可以预处理出dis数组了
那么d(x,y)=dis[x]+dis[y]-2*dis[LCA(x,y)]
现在只需要求LCA就行了,而求LCA可以倍增和树剖来求
我是用的树剖求LCA,因为我觉得树剖优美 (逃
而对于树上路径覆盖,我们直接树上差分就行了
这题显然是对于树上边的差分
我们设差分数组为C,每一次我们都让那些大于二分出的路径值大的路径的
C[x]++,C[y]++,C[LCA(x,y)]-=2 (差分一下)
那么每次只需要判断是否存在一条边的边权k>=最长路径-二分的路径值,同时这些路径的距离都是比二分值大的,就行了
判断时要每次把儿子的差分值统计到父亲中
光说可能有些难懂,下面放代码
下面的变量可能有些小问题,因为防止重复(以及个人习惯),可能存在一些异类格格不入的变量,请谅解
(本人代码极丑,各位不喜勿喷)
PS:代码里也有解释哦~
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define re register
using namespace std;
typedef long long ll;
const int inf=1e9+7;
inline int read()
{
int p=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return f*p;}
const int maxn=300003;
struct Edge
{
int from,to,w,id;
}p[maxn<<1];
struct query
{
int x,y,lca,d;
}A[maxn];
int n,m,cnt,head[maxn<<1],C[maxn],dis[maxn];
int fa[maxn],depth[maxn],top[maxn],heavy[maxn],size[maxn];
int val[maxn],dnf[maxn],tot,R,L;
inline void add_edge(int x,int y,int W)//加边
{
cnt++;
p[cnt].from=head[x];
head[x]=cnt;
p[cnt].to=y;
p[cnt].w=W;
}
inline void dfs1(int x,int f)
//树剖dfs1:处理每个点的父亲fa,深度depth,子树大小size,dfs序dnf
{
fa[x]=f,depth[x]=depth[f]+1,size[x]=1,dnf[++tot]=x;
for(re int i=head[x];i;i=p[i].from)
{
int y=p[i].to;
if(y==f)continue;
val[y]=p[i].w;
dis[y]=dis[x]+p[i].w;
dfs1(y,x);
size[x]+=size[y];
if(!heavy[x]||size[y]>size[heavy[x]])
heavy[x]=y;
}
}
inline void dfs2(int x,int t)//树剖dfs2:处理重链
{
top[x]=t;
if(!heavy[x])return ;
dfs2(heavy[x],t);
for(re int i=head[x];i;i=p[i].from)
{
int y=p[i].to;
if(y==fa[x]||y==heavy[x])continue;
dfs2(y,y);
}
}
inline int LCA(int x,int y)//树剖求LCA
{
while(top[x]!=top[y])
{
if(depth[top[x]]<depth[top[y]])swap(x,y);
x=fa[top[x]];
}
return depth[x]<=depth[y]?x:y;
}
//=================================以上是树剖常规操作
inline int check(int lim,int sum=0)//二分答案检验,如上所述
{
memset(C,0,sizeof(C));//注意每一次都要清空C数组
for(re int i=1;i<=m;i++)
if(A[i].d>lim)//树上(边)差分
{
C[A[i].x]++,C[A[i].y]++,C[A[i].lca]-=2;
sum++;
}
for(re int i=n;i>=1;i--)
{
C[fa[dnf[i]]]+=C[dnf[i]];//每次差分值都累加到父亲节点
if(val[dnf[i]]>=R-lim&&C[dnf[i]]==sum)
//存在一条路径满足上述条件则可行
return 1;
}
return 0;//否则无解
}
inline int Binary_search(int llim,int rlim,int mid=0)//二分答案
{
while(llim<rlim)
{
mid=(llim+rlim)>>1;
if(check(mid))rlim=mid;
else llim=mid+1;
}
return llim;
}
int main()
{
// freopen("transport.in","r",stdin);
// freopen("transport.out","w",stdout);
//这是校内模拟赛的考试题= =光荣爆蛋
n=read(),m=read();
for(re int i=1;i<n;i++)
{
int x=read(),y=read(),w=read();
add_edge(x,y,w);
add_edge(y,x,w);
L=max(L,w);//统计最大边权
}
dfs1(1,0);dfs2(1,1);//树剖预处理
for(re int i=1;i<=m;i++)//预处理每一次请求的lca和距离
{
A[i].x=read(),A[i].y=read();
A[i].lca=LCA(A[i].x,A[i].y);
A[i].d=dis[A[i].x]+dis[A[i].y]-2*dis[A[i].lca];
R=max(R,A[i].d);
}
printf("%d\n",Binary_search(R-L,R+1));//二分答案
return 0;
}好了,到这里其实就没什么了,本题已经差不多讲完了
附加一个链接,这个链接主要是讲差分的(包含差分和树上差分)
本人认为读完之后受益匪浅,推荐大家去看一看
链接: dalao的博客
(反正至少我的乱搞算法想到了里面讲的树上差分)
最后,感谢你的阅读!
(无耻的)推一波我的blog:
https://www.luogu.org/blog/new2zy/
拜拜~~~