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
11
Http
Luogu: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
",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;
}