【题解】P4886 快递员
淀粉质好题！！！加深了我对点分治的理解。最近分治学了好多啊。
题目大意
给定你一颗有边权的树，再给你\(m\)和点对，请你在树上选出来一个点，使得所有点对到这个点的距离的最大值最小。请你输出最小的最长距离。
数据范围
对于\(100\%\)的数据，\(n,m\le10^5,w_i \le 10^3\)
思路
刚开始看到这个题目，以为题干在暗示我二分答案。于是设计一个这样的算法
先二分，得到一个\(log10^8=26\)的系数，得到一个答案\(k\)后，每次先枚举\(O(m)\)的点，然后在树剖的线段树上把这\(2m\)个点扩展\(k\)距离，最后查询是否有点被遍历了\(2m\)次，返回\(true \ or \ false\) 实现二分。复杂度大约\(=6\times10^8\)，无奈过不去。
先分析题目的一个重要性质！假设我们已经选中了一个点，并且发现产生最大距离的点对当中，有一条路径经过了那个点，那么此时一定是最优答案！
怎么得到的？你看我随便移开到不是这个端点的地方，最大答案只会变大啊！
那么我们可以设计\(O(nm)\)的算法，直接枚举我们选择的快递中心\(v\)，然后\(O(n)\)得到所有点到此点的距离，和若删去此点后在的子树的编号，直接\(O(m)\)枚举所有的点对，查询\(dis_{i_1}+dis_{i_2}\)得到距离最大值，查询是否在同一颗子树里得到改点在它们的路径上。但这样显然过不去。
\(Solution\)
考虑优化，假若我发现对于最大值产生贡献的点对都在我的一颗子树内，那么我就往这颗子树里走，这样才有一点可能更新更优解。这样就可以把其他子树给剪枝了不是？而且继续考虑产生最优解时的性质，如果存在多组对最大值产生贡献的点对在不同的子树内，此时我同样一定是最优解。把问题缩小变成的量\(=\)我跳的那个子树的大小
联系淀粉质，考虑怎么样可以把剪枝最大化，直接跳树的重心啊，这样每次要么确定答案，要么把问题化为至多\(n'=logn\)的大小，这样就是\(O(nlogn)\)了。
讲一讲写点分治会犯的错误吧。主要是我不熟练，也很傻。
-
共产风
意思就是不清空上次统计答案造成的影响
- 没有清零当前根的\(dis\)
- 不回溯自己的树状数组，线段树等
-
浮夸风
打字前没有\(orz \ yyb\)
-
瞎指挥
意思就是跳随机点了！
和随机分治有异曲同工之妙
产生随机跳的情况包括但不限于：
- 不初始化\(rt\)
- 找错\(rt\)
- 遍历了\(usd\)的点
- 不调用\(rt\)
- 不重置\(sum\)
上好看的代码
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t)
#define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;++t)
#define ERP(t,a) for(register int t=head[a];t;t=e[t].nx)
#define midd register int mid=(l+r)>>1
#define TMP template < class ccf >
TMP inline ccf qr(ccf b){
register char c=getchar();register int q=1;register ccf x=0;
while(c<48||c>57)q=c==45?-1:q,c=getchar();
while(c>=48&&c<=57)x=x*10+c-48,c=getchar();
return q==-1?-x:x;}
TMP inline ccf Max(ccf a,ccf b){return a<b?b:a;}
TMP inline ccf Min(ccf a,ccf b){return a<b?a:b;}
TMP inline ccf Max(ccf a,ccf b,ccf c){return Max(a,Max(b,c));}
TMP inline ccf Min(ccf a,ccf b,ccf c){return Min(a,Min(b,c));}
TMP inline ccf READ(ccf* _arr,int _n){RP(t,1,_n)_arr[t]=qr((ccf)1);}
//----------------------template&IO---------------------------
const int maxn=1e5+15;
struct E{
int to,nx,w;
}e[maxn<<1];
int n,m;
int F[maxn],T[maxn];
int head[maxn];
int cnt;
inline void add(int fr,int to,int w,bool f){
e[++cnt]=(E){to,head[fr],w};
head[fr]=cnt;
if(f) add(to,fr,w,0);
}
bool usd[maxn];
int d[maxn];
int spc[maxn];
int siz[maxn];
int sum,rt;
int dan[maxn];
int fans=0x3f3f3f3f;
int q[maxn];
inline void can(){
printf("%d\n",fans);
exit(0);
}
void getroot(int now,int last){
siz[now]=spc[now]=1;
ERP(t,now){
if(!usd[e[t].to]&&e[t].to!=last){
getroot(e[t].to,now);
siz[now]+=siz[e[t].to];
spc[now]=Max(spc[now],siz[e[t].to]);
}
}
spc[now]=Max(spc[now],sum-siz[now]);
if(spc[now]<spc[rt]||!rt) rt=now;
}
void getdis(int now,int last,int ew,int id){
dan[now]=id;
d[now]=d[last]+ew;
ERP(t,now){
if(e[t].to!=last){
getdis(e[t].to,now,e[t].w,id);
}
}
}
inline int calc(int now){
dan[now]=now;d[now]=0;
ERP(t,now) getdis(e[t].to,now,e[t].w,e[t].to);
register int top=0;
register int ans=0;
register int ret=0;
RP(t,1,m)
if(d[F[t]]+d[T[t]]==ans) q[++top]=t;
else if(d[F[t]]+d[T[t]]>ans) ans=d[F[t]]+d[T[t]],q[top=1]=t;
fans=Min(fans,ans);
RP(t,1,top){
if(dan[F[q[t]]]!=dan[T[q[t]]]) can();
else{
if(!ret) ret=dan[F[q[t]]];
if(ret!=dan[F[q[t]]]) can();
}
}
return ret;
}
void divd(int now){
usd[now]=1;
register int t=calc(now);
if(usd[t]) can();
sum=siz[t];rt=0;
getroot(t,0);
divd(rt);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
sum=n=qr(1);
m=qr(1);
register int t1,t2,t3;
RP(t,1,n-1){
t1=qr(1);t2=qr(1);t3=qr(1);
add(t1,t2,t3,1);
}
RP(t,1,m)
F[t]=qr(1),T[t]=qr(1);
usd[0]=1;
getroot(1,0);
divd(rt);
cout<<fans<<endl;
return 0;
}