题目描述：
绿老师和弗绿兹是好朋友。 绿老师决定和弗绿兹在一棵 N 个节点的树上玩一个游戏，边有边权，有 M 个点对 (ai,bi)，绿老师 选择一个 i，从 ai 走到 bi，弗绿兹选择一个 j，从 aj 走到 bj，他们希望他们走的距离之和最大。 但是这些点对被原谅了，绿老师走会从 ai 走到 aj，而弗绿兹会从 bi 走到 bj ，求他们走的距离之和 的最大值。
算法标签：点分治
思路：
考虑写点分治，对于ai,aj的路线经过当前rt,我们可以预处理处dist(ai,x)和dist（x,aj），这个路径距离只与一个点相关，可以看做是每个点的权值，于是相当于直接求最远点对，每次求出最大和次大，维护最远点对且保证其统计到的答案的两点不在一棵子树上。
！！！点分治很不熟练，哭辽！
以下代码：
#include<bits/stdc++.h> #define il inline #define LL long long #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=1e5+5;const LL inf=1e18; bool vis[N];vector<int> v[N];LL m1[N],m2[N],ans,dist[N],val[N]; int n,m,head[N],ne[N<<1],to[N<<1],w[N<<1],cnt,mn[N<<1][20]; int id[N],tot,Lg[N<<1],rt,son[N],size,d[N],sz[N],fa[N],fir[N],q[N],b[N],b0; il int read(){int x;char ch;_(!);x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return x;} il void insert(int x,int y,int z){ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;w[cnt]=z;} il int Min(int x,int y){return d[x]<d[y]?x:y;} il void dfs(int x,int fa){ mn[id[x]=++tot][0]=x; for(int i=head[x];i;i=ne[i]){ if(fa==to[i])continue; d[to[i]]=d[x]+1;dist[to[i]]=dist[x]+w[i]; dfs(to[i],x);mn[++tot][0]=x; } } il void init(){ for(int i=2;i<=tot;i++)Lg[i]=Lg[i>>1]+1; for(int j=1;j<=Lg[tot];j++)for(int i=1;i+(1<<j)-1<=tot;i++) mn[i][j]=Min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]); } il void getrt(int x,int fa){ sz[x]=1;son[x]=0; for(int i=head[x];i;i=ne[i]){ if(fa==to[i]||vis[to[i]])continue; getrt(to[i],x);sz[x]+=sz[to[i]]; son[x]=max(son[x],sz[to[i]]); } son[x]=max(son[x],size-sz[x]); if(!rt||son[x]<son[rt])rt=x; } il void s1(int x){ vis[x]=1; for(int i=head[x];i;i=ne[i]){ if(vis[to[i]])continue; size=sz[to[i]];rt=0;getrt(to[i],x); fa[rt]=x;s1(rt); } } il void dfs1(int x,int fa,LL dis){ for(int i=0;i<v[x].size();i++)b[++b0]=v[x][i],val[b0]=dis; for(int i=head[x];i;i=ne[i]) if(!vis[to[i]]&&fa!=to[i])dfs1(to[i],x,dis+(LL)w[i]); } il int Lca(int x,int y){ int l=id[x],r=id[y];if(l>r)swap(l,r);int k=Lg[r-l+1]; return Min(mn[l][k],mn[r-(1<<k)+1][k]); } il LL getd(int x,int y){ int lca=Lca(x,y); return dist[x]+dist[y]-dist[lca]*2; } il void add(int x,LL v){ for(int u=x,la=0;u;la=u,u=fa[u]){ LL kk=v+getd(x,u); if(kk>=m1[u]){ if(fir[u]==la)m1[u]=kk; else m2[u]=m1[u],m1[u]=kk,fir[u]=la; } else if(kk>m2[u]&&fir[u]!=la)m2[u]=kk; } } il LL query(int x){ LL res=-inf; for(int u=x,la=-1;u;la=u,u=fa[u]){ if(fir[u]==la)res=max(res,getd(u,x)+m2[u]); else res=max(res,getd(u,x)+m1[u]); } return res; } il void cl(int x){ for(;x;x=fa[x]){ if(m1[x]==-inf)break;m1[x]=m2[x]=-inf,fir[x]=-1; } } il void solve(int x){ vis[x]=1;int tot=0; for(int i=0;i<v[x].size();i++) q[++tot]=v[x][i],add(v[x][i],0); for(int i=head[x];i;i=ne[i]){ if(vis[to[i]])continue; b0=0;dfs1(to[i],x,w[i]); for(int j=1;j<=b0;j++)ans=max(ans,query(b[j])+val[j]); if(ne[i])for(int j=1;j<=b0;j++)add(b[j],val[j]),q[++tot]=b[j]; } for(int i=1;i<=tot;i++)cl(q[i]); for(int i=head[x];i;i=ne[i]){ if(vis[to[i]])continue; rt=0;size=sz[to[i]]; getrt(to[i],x);solve(rt); } } int main() { n=read();m=read(); for(int i=1;i<n;i++){int x=read(),y=read(),z=read();insert(x,y,z);insert(y,x,z);} d[1]=1;dfs(1,0);init();size=n;rt=0;getrt(1,0);s1(rt); for(int i=1;i<=n;i++)vis[i]=0,m1[i]=-inf,m2[i]=-inf,fir[i]=-1; for(int i=1;i<=m;i++){int x=read(),y=read();v[x].push_back(y);} rt=0;size=n;getrt(1,0);solve(rt); printf("%lld ",ans); return 0; }