Luogu 2680 NOIP 2015 运输计划（树链剖分，LCA，树状数组，树的重心，二分，差分）...

ゝ一世哀愁。 2021-10-01 03:02 261阅读 0赞

# Luogu 2680 NOIP 2015 运输计划（树链剖分，LCA，树状数组，树的重心，二分，差分） #

### Description ###

L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物

流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之 间不会产生任何干扰。

为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后, 这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的 物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段 性工作所需要的最短时间是多少?

### Input ###

第一行包括两个正整数 n、m,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 1 到 n 编号。

接下来 n-1 行描述航道的建设情况,其中第 i 行包含三个整数 ai, bi 和 ti,表示第

i 条双向航道修建在 ai 与 bi 两个星球之间,任意飞船驶过它所花费的时间为 ti。

接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j个 运输计划是从 uj 号星球飞往 vj 号星球。

### Output ###

输出 共1行,包含1个整数,表示小P的物流公司完成阶段性工作所需要的最短时间。

### Sample Input ###

6 3  
1 2 3  
1 6 4  
3 1 7  
4 3 6  
3 5 5  
3 6  
2 5  
4 5

### Sample Output ###

### Http ###

Luogu:[https://www.luogu.org/problem/show?pid=2680][https_www.luogu.org_problem_show_pid_2680]

### Source ###

树链剖分，最近公共祖先LCA，树的重心，二分，差分，树状数组

## 题目大意 ##

给出一棵边权树，现在给定若干对点，要求选择一条树边使其权值为0，使得所有的点对的距离的最大值最小。

## 解决思路 ##

基本的思路是先通过求最近公共祖先LCA来求得这若干对点对的距离。按照距离从大到小排序后，二分最大的距离\\(mid\\)，将那些距离大于\\(mid\\)的连接点对的路径打上标记，设有k个这样的路径。找出那些这k条路径都覆盖的边，判断如果把这条边距离设为0是否可以使得所有的路径长度都小于\\(mid\\)，如果可以，则说明该\\(mid\\)是可行的，否则不行。  
但单纯的照上面这样做是不行的，我们考虑优化。  
首先是求这若干组点对的距离。我们知道在树上求两点之间的距离与LCA有关，而求LCA有两种算法，一种是倍增法，另一种是树链剖分。这里为了方面后面的差分，同时也是为了减小常数，选用**树链剖分**的方法。我们将树按照轻重剖分成轻链和重链，将树上的问题转换成若干区间的问题。  
接下来考虑如何维护区间。由题可知，本题需要维护的是路径长度，也就是若干边权之和。但对于边权的操作远不如点权方便，所以我们**把边权转化成为点权**，具体方法是将点\\(u\\)到其父亲节点\\(f\\)的边的权转化成为点\\(u\\)的点权。这里需要注意的是，将边权转化成为点权之后，两个点\\(u,v\\)之间的路径长度就**不是**\\(u\\)到\\(lca(u,v)\\)的点权和加\\(v\\)到\\(lca(u,v)\\)的点权和了，因为\\(lca(u,v)\\)的点权是到其父亲的边权，不在\\(u\\)到\\(v\\)的路径上，所以在向上跳转的时候要跳到\\(lca\\)的深度+1的点。同样需要改变的也包括区间查询和差分。  
至于维护这个和，因为只有查询和插入，所以这里考虑使用常数更小的**树状数组**来实现。  
现在考虑将选出的长度大于\\(mid\\)的路径标记。可以将路径上的每一条边标记+1，然后可以知道，如果有k条这样的路径，那么标记为k的边就是这k条路径都覆盖的。但是暴力标记是不行的。我们发现每次都是将k条路径都标记完后再操作，所以我们可以考虑差分。而又因为我们用树链剖分将树划分成链，所以可以参考求解LCA的在链上跳转的方式，在重链的top位置++，而在当前位置+1的地方--，注意，这些位置都是在点的新编号的位置（也就是在点在树状数组中的编号），因为这样就变成区间差分了。但是最后一条链的起始位置（即lca的位置）要+1，具体原因是我们把边权转化成了点权，而lca的点权代表的边权不在路径上。  
最后来判断是否可行。因为最长路径一定会被选，所以我们在从\\(1~n\\)累加差分数组，当累加器\\(ret==k\\)时，判断最长路径减去当前点\\(i\\)对应的点权是否小于当前二分的\\(mid\\)，如果存在一条这样的边，则可行，否则不行。  
另外，我们知道在树上操作的效率一定程度上取决于对根节点的选取，所以我们可以在最开始求出树的重心，并以重心为根，这样可以提高效率。

## 代码 ##

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define lowbit(x) ((x)&(-x)) const int maxN=300101; const int maxM=300101; const int inf=2147483647; int n; class Edge//边 { public: int u,v,w; }; class TreeArr//树状数组 { public: int A[maxN]; TreeArr() { memset(A,0,sizeof(A)); return; } void Add(int pos,int x)//插入 { while (pos<=n) { A[pos]=A[pos]+x; pos=pos+lowbit(pos); } return; } int Sum(int x)//求和1~x { int ret=0; while (x>0) { ret=ret+A[x]; x=x-lowbit(x); } return ret; } int query(int l,int r)//求区间和 { return Sum(r)-Sum(l-1); } }; class Question//对于每一条路径 { public: int u,v,w; }; bool operator < (Question A,Question B)//按照路径长度降序排序 { return A.w>B.w; } int qus; int root,rootsize;//重心，以及对应的最大子树-最小子树 int longestpath=0;//最长路径 //Graph 原来树中的data int cnt=0; int Head[maxN]; int Next[maxN*2]; Edge E[maxN*2]; int Node_W[maxN];//边权转化后的点权 //Tree_Chain 树链剖分维护的data int Depth[maxN];//深度 int Father[maxN];//父节点编号 int Top[maxN];//链顶 int Size[maxN];//大小 int HeavySon[maxN];//重儿子 int Id[maxN];//Id[i]表示树状数组中i对应的原节点编号。若Id[i]==j则dfn[j]==i int dfn[maxN];//原节点i对应的在树链剖分中分配的新编号 //TreeArr TreeArr TA;//树状数组 //Q Question Q[maxM];//点对和路径 //Insert int Num[maxN];//差分数组 int read(); void Add_Edge(int u,int v,int w); void dfs(int u,int father);//求重心 void dfs1(int u,int father);//树链剖分第一遍dfs void dfs2(int u,int nowTop);//树链剖分第二遍dfs int Calc_Path(int u,int v);//计算u到v的路径长度 bool check(int nowmid);//检查当前最大距离是否合法 void Insert(int u,int v);//将u到v的路径差分标记 int main() { memset(Head,-1,sizeof(Head)); rootsize=inf; n=read(); qus=read(); for (int i=1;i<n;i++)//读入边 { int u,v,w; u=read(); v=read(); w=read(); Add_Edge(u,v,w); Add_Edge(v,u,w); } //处理出重心 dfs(1,1); //树链剖分 Depth[1]=1; dfs1(root,root); cnt=0; dfs2(root,root); for (int i=1;i<=n;i++)//将边权转化成点权并存入树状数组 TA.Add(dfn[i],Node_W[i]); //求解路径 for (int i=1;i<=qus;i++) { Q[i].u=read(); Q[i].v=read(); Q[i].w=Calc_Path(Q[i].u,Q[i].v); longestpath=max(Q[i].w,longestpath);//选出最长路径 //cout<<Q[i].w<<endl; } sort(&Q[1],&Q[qus+1]);//将路径排序 int l=1,r=longestpath;//二分 int Ans; do { int mid=(l+r)/2; if (check(mid))//检查 { Ans=mid; r=mid-1; } else l=mid+1; } while (l<=r); printf("%d\n",Ans); return 0; } int read() { int x=0; char ch=getchar(); while ((ch>'9')||(ch<'0')) ch=getchar(); while ((ch<='9')&&(ch>='0')) { x=x*10+ch-48; ch=getchar(); } return x; } void Add_Edge(int u,int v,int w) { cnt++; Next[cnt]=Head[u]; Head[u]=cnt; E[cnt].u=u; E[cnt].v=v; E[cnt].w=w; return; } void dfs(int u,int father)//求重心 { Size[u]=1; int mx=0,mn=inf;//分别记录最大子树和最小子树 for (int i=Head[u];i!=-1;i=Next[i]) { int v=E[i].v; if (v==father) continue; dfs(v,u); Size[u]+=Size[v]; if (Size[v]>mx) mx=Size[v]; else if (Size[v]<mn) mn=Size[v]; } if (n-Size[u]>mx) mx=n-Size[u]; else if (n-Size[u]<mn) mn=n-Size[u]; if ((mx!=0)&&(mn!=inf)&&(mx-mn<rootsize)) { root=u; rootsize=mx-mn; } return; } void dfs1(int u,int father)//树链剖分第一次dfs { Size[u]=1; HeavySon[u]=0; for (int i=Head[u];i!=-1;i=Next[i]) { int v=E[i].v; if (v==father) continue; Father[v]=u; Depth[v]=Depth[u]+1; Node_W[v]=E[i].w;//将边权转换成点权 dfs1(v,u); Size[u]=Size[u]+Size[v]; if ((HeavySon[u]==0)||(Size[HeavySon[u]]<Size[v])) HeavySon[u]=v; } return; } void dfs2(int u,int nowTop)//树链剖分第二次dfs { cnt++; dfn[u]=cnt; Id[cnt]=u; Top[u]=nowTop; if (HeavySon[u]==0) return; dfs2(HeavySon[u],nowTop); for (int i=Head[u];i!=-1;i=Next[i]) if ((E[i].v!=Father[u])&&(E[i].v!=HeavySon[u])) dfs2(E[i].v,E[i].v); return; } int Calc_Path(int u,int v)//计算u到v的路径长 { int path=0; while (Top[u]!=Top[v]) { if (Depth[Top[u]]<Depth[Top[v]]) swap(u,v); path+=TA.query(dfn[Top[u]],dfn[u]); u=Father[Top[u]]; } if (Depth[u]>Depth[v]) swap(u,v); return path+TA.query(dfn[u]+1,dfn[v]); } bool check(int nowmid)//检查合法性 { int pos=0; while (Q[pos+1].w>nowmid)//将路径长度大于mid的路径加入差分 { pos++; Insert(Q[pos].u,Q[pos].v); } int now=0; for (int i=1;i<=n;i++) { now=now+Num[i]; Num[i]=0; if ((now==pos)&&(longestpath-Node_W[Id[i]]<=nowmid))//当当前第i个点被所有pos条不满足的路径都覆盖时，若最长路径减去其点权比nowmid小，说明能够满足 { for (int j=i+1;j<=n;j++) Num[j]=0; return 1; } } return 0; } void Insert(int u,int v)//差分 { while (Top[u]!=Top[v]) { if (Depth[Top[u]]<Depth[Top[v]]) swap(u,v); Num[dfn[Top[u]]]++; Num[dfn[u]+1]--;//注意这里+1 u=Father[Top[u]]; } if (Depth[u]>Depth[v]) swap(u,v); Num[dfn[u]+1]++;//常规的差分这里是不要+1的，但这里需要，因为dfn[u]所对应的边不在u到v的路径上 Num[dfn[v]+1]--; return; }

转载于:https://www.cnblogs.com/SYCstudio/p/7629268.html

[https_www.luogu.org_problem_show_pid_2680]: https://www.luogu.org/problem/show?pid=2680