题解 P4886 【快递员】

· · 题解

完了...没高中读了QwQ，我要去打工送快递！！！QwQ

题解

这题其实还是挺好玩的。

首先随便钦定一个点，临时作为快递中心 。

然后可以O(n)计算出每一组点对到快递中心的距离和。设点对到快递中心最大距离和为Max，可能有多个点对到快递中心的距离和都是Max那么就把它们都存下来。

如果当前的快递中心在任意一组距离最大的点对之间最短路径上，那么答案就是Max不可能再小了。

如果有任意两组距离最大的点对，一组在当前快递中心的一棵子树里，另一组在另一棵子树里，那么答案同样也无法更小。

否则答案最优时的快递中心就有可能在当前唯一一棵有点对的子树中，那么就取这棵子树的重心作为临时快递中心，然后递归。由于每次取的都是重心，所以只会递归\log n层，总时间复杂度为O(n\log n)。

代码

#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=100005;
int n,m,u[maxn],v[maxn],tot,lnk[maxn],son[maxn*2],w[maxn*2],nxt[maxn*2],sum,siz[maxn],maxp[maxn],rt,sub[maxn],dist[maxn],que[maxn],ans=1000000000;bool vis[maxn];
inline int read()
{
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f;
}
inline void add_e(int x,int y,int z){tot++;son[tot]=y;w[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;}
void GetRoot(int now,int fa)     //找重心
{
    siz[now]=1;maxp[now]=0;
    for(int i=lnk[now];i;i=nxt[i])
    {
        if(vis[son[i]]||son[i]==fa) continue;
        GetRoot(son[i],now);siz[now]+=siz[son[i]];
        if(siz[son[i]]>maxp[now]) maxp[now]=siz[son[i]];
    }
    if(sum-siz[now]>maxp[now]) maxp[now]=sum-siz[now];
    if(maxp[now]<maxp[rt]) rt=now;
}
void GetDist(int now,int fa,int st)
{
    sub[now]=st;
    for(int i=lnk[now];i;i=nxt[i])
        if(son[i]!=fa)
            {dist[son[i]]=dist[now]+w[i];GetDist(son[i],now,st);}
}
inline void Print(){printf("%d\n",ans);exit(0);}   //输出答案
void Solve(int now)
{
    if(vis[now]) Print();
    vis[now]=true;dist[now]=0;
    for(int i=lnk[now];i;i=nxt[i])
        {dist[son[i]]=w[i];GetDist(son[i],now,son[i]);} //先暴力计算距离
    int Max=0,len=0,las=0;
    for(int i=1;i<=m;i++)
    {
        if(dist[u[i]]+dist[v[i]]>Max){len=1;que[len]=i;Max=dist[u[i]]+dist[v[i]];}
        else if(dist[u[i]]+dist[v[i]]==Max) que[++len]=i; //刷最大距离和
    }
    if(Max<ans) ans=Max;
    for(int i=1;i<=len;i++)
    {
        if(sub[u[que[i]]]!=sub[v[que[i]]]) Print();   //分情况考虑答案
        if(!las) las=sub[u[que[i]]];
        if(sub[u[que[i]]]!=las) Print(); 
    }
    rt=0;sum=siz[las];GetRoot(las,0);Solve(rt);    //递归解决
}
int main()
{
    n=read();m=read();
    for(int i=1;i<n;i++)
    {
        int a=read(),b=read(),c=read();
        add_e(a,b,c);add_e(b,a,c);
    }
    for(int i=1;i<=m;i++){u[i]=read();v[i]=read();}
    sum=maxp[0]=n;GetRoot(1,0);Solve(rt);
    Print();
    return 0;
}