题解 P2993 【[FJOI2014]最短路径树问题】

· · 题解

主要考察知识：点分治+最短路径生成树。

PART #1:最短路径生成树

相当于在跑dijkstra的时候记个路径所构成的树。

证明：1.除1外每个点均连一条边，故为n-1条边。

2.每个点均向最短路严格小于自己的点连边，故无环。

则一定为树，证毕。

注意：由于此题求最长路径，故选取最长的边，如下：

if(dis[t]>dis[x]+w[i]){
    dis[t]=dis[x]+w[i];
    pre[t]=x;val[t]=w[i];
    q.push(make_pair(-dis[t],t));
}else if(dis[t]==dis[x]+w[i]&&w[i]>val[t]){
    pre[t]=x;val[t]=w[i];
}

PART #2:点分治

请问，在这棵最短路径树上，最长的包含K个点的简单路径长度为多长？

长度为该最长长度的不同路径有多少条？

在树上询问定长路径相关问题是经典的点分治问法。

还不会点分治的同学推荐看这篇博客

点分时处理对应长度出现的最大值及出现次数。

注意：1.及时清零数组以防超时。

2.处理完每个子数再递归，以防数组在下层中被改变。

时间复杂度O(nlogn)

完整代码如下，仅供参考：

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=2e5+10;
const int mod=1e9+7;
int n,m,k;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
int beg[maxn],nex[maxn],to[maxn],w[maxn],e;
inline void add(int x,int y,int z){
    e++;nex[e]=beg[x];
    beg[x]=e;to[e]=y;w[e]=z;
}
int dis[maxn],vis[maxn],pre[maxn],val[maxn];
priority_queue<pair<int,int> >q;
int ans,num,rt,mx,size,siz[maxn],son[maxn];
inline void getrt(int x,int fa){
    siz[x]=1;son[x]=0;
    for(int i=beg[x];i;i=nex[i]){
        int t=to[i];
        if(t==fa||vis[t])continue;
        getrt(t,x);
        siz[x]+=siz[t];
        if(son[x]<siz[t])son[x]=siz[t];
    }
    if(son[x]<size-siz[x])son[x]=size-siz[x];
    if(mx>son[x])mx=son[x],rt=x;
}
int bot[maxn],cou[maxn],zyf[maxn],whm[maxn],tmp;
inline void calc(int x,int fa,int dist,int dep){
    if(zyf[dep]<dist){
        zyf[dep]=dist;
        whm[dep]=1;
    }else if(zyf[dep]==dist)
        whm[dep]++;
    if(dep>tmp)tmp=dep;
    for(int i=beg[x];i;i=nex[i]){
        int t=to[i];
        if(t==fa||vis[t])continue;
        calc(t,x,dist+w[i],dep+1);
    }
}
inline void solve(int x){
    cou[0]=vis[x]=1;
    int dep=0;
    for(int i=beg[x];i;i=nex[i]){
        int t=to[i];tmp=0;
        if(vis[t])continue;
        calc(t,x,w[i],1);
        if(tmp>dep)dep=tmp;
        for(int j=1;j<=tmp;j++)
            if(cou[k-1-j])
                if(ans<zyf[j]+bot[k-1-j]){
                    ans=zyf[j]+bot[k-1-j];
                    num=whm[j]*cou[k-1-j];
                }else if(ans==zyf[j]+bot[k-1-j])
                    num+=whm[j]*cou[k-1-j];
        for(int j=1;j<=tmp;j++)
            if(zyf[j]>bot[j]){
                bot[j]=zyf[j];
                cou[j]=whm[j];
            }else if(zyf[j]==bot[j])
                cou[j]+=whm[j];
        for(int j=1;j<=tmp;j++)
            zyf[j]=whm[j]=0;
    }
    for(int i=0;i<=dep;i++)
        bot[i]=cou[i]=0;
    for(int i=beg[x];i;i=nex[i]){
        int t=to[i];
        if(vis[t])continue;
        rt=0,mx=inf,size=siz[t];
        getrt(t,x);
        solve(rt);
    }
}
int main(){
    n=read(),m=read(),k=read();
    int x,y,z;
    for(int i=1;i<=m;i++){
        x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;q.push(make_pair(0,1));
    while(!q.empty()){
        x=q.top().second;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=beg[x];i;i=nex[i]){
            int t=to[i];
            if(dis[t]>dis[x]+w[i]){
                dis[t]=dis[x]+w[i];
                pre[t]=x;val[t]=w[i];
                q.push(make_pair(-dis[t],t));
            }else if(dis[t]==dis[x]+w[i]&&w[i]>val[t]){
                pre[t]=x;val[t]=w[i];
            }
        }
    }
    e=0;memset(beg,0,sizeof(beg));
    for(int i=2;i<=n;i++)
        add(i,pre[i],val[i]),add(pre[i],i,val[i]);
    mx=inf,size=n,rt=0;
    memset(vis,0,sizeof(vis));
    getrt(1,0);
    solve(rt);
    printf("%d %d\n",ans,num);
    return 0;
}

深深地感到自己的弱小。