P4886 快递员 点分治

　　题意：给定一个边权树  和m个点对   求一个点 最小化到m个点对的距离的最大值       与点对(a,b)的距离定义为 dis(x-a) + dis(x-b)

点分治思想的运用

先随便以一个点作为所求的点  并记录所有的最大距离点对

然后遍历最大距离点对

如果一个点对两个点在根的两棵子树上  那么显然不可能再减小答案了  return

所以经过上面的筛选每个点对一定在同棵子树

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define inf 0x3f3f3f3f
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
const int N=2e6+10;
int head[N],vis[N],sum,pos,n,m,x[N],y[N],maxx,root,siz[N],maxson[N],ans,dep[N],belong[N],p[N],a,b,c;
struct Edge{int to,nex,v;}edge[N<<1];
void add(int a,int b,int c){edge[++pos]=(Edge){b,head[a],c};head[a]=pos;}
void getroot(int x,int fa)
{
    siz[x]=1;maxson[x]=0;
    for(int i=head[x];i;i=edge[i].nex)
    {
        int v=edge[i].to;
        if(v==fa||vis[v])continue;
        getroot(v,x);siz[x]+=siz[v];
        maxson[x]=max(maxson[x],siz[v]);
    }
    maxson[x]=max(maxson[x],sum-siz[x]);
    if(maxson[x]<maxson[root])root=x;
}
void dfs(int x,int fa,int val,int rt)
{
    dep[x]=val;
    belong[x]=rt;
    for(int i=head[x];i;i=edge[i].nex)
    if(edge[i].to!=fa)dfs(edge[i].to,x,val+edge[i].v,rt);
}
void solve(int u)
{
    if(vis[u])return ;vis[u]=1;
    
    for(int i=head[u];i;i=edge[i].nex)
    dfs(edge[i].to,u,edge[i].v,edge[i].to);
    dep[u]=p[0]=0;
    int Max=0,last=0;
    rep(i,1,m)
    if(dep[x[i]]+dep[y[i]]>Max)Max=dep[x[i]]+dep[y[i]],p[p[0]=1]=i;
    else if(dep[x[i]]+dep[y[i]]==Max)p[++p[0]]=i;
    ans=min(ans,Max);

    rep(i,1,p[0])
    {
        if(belong[x[ p[i] ]]!=belong[y[ p[i] ]])return;//跨过了该节点 那么怎么都不会缩小了
        else 
        {
            if(!last)last=belong[x[p[i]]];
            else if(last!=belong[x[p[i]]])
            return ;
        }
    }
    sum=siz[last];root=0;
    getroot(last,u);
    solve(root);
}
int main()
{
    scanf("%d%d",&n,&m);
    rep(i,1,n-1)
    scanf("%d%d%d",&a,&b,&c),add(a,b,c),add(b,a,c);
    rep(i,1,m)scanf("%d%d",&x[i],&y[i]);
    sum=maxson[0]=n;
    root=0;
    getroot(1,0);
    ans=inf;
    solve(root);
    cout<<ans;
    return 0;
}      

View Code