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

· · 题解

欢迎来我的Blog

LG传送门

B站传送门

长链剖分练手好题。

如果你还不会长链剖分的基本操作，可以看看我的总结。

这题本来出的很没水平，就是dijkstra（反正我是不用SPFA）的板子强行套个点分治的板子，两者之间没有任何关联。但我偏要写长链剖分。

首先给你的是一张图，要转成一棵题目所要求的树，先把出边按到达点的编号排个序再跑个单源最短路，然后一遍dfs把树建出来就好了。这不是本文的重点（如果用点分治也要这样写），如果没搞懂看看代码就好了。

建出一棵树之后，把某个点连向其父亲的边的边权定为这个点的点权（我写长链剖分习惯处理点权），然后就可以写DP了，按照一般套路先写n^2DP。容易想到设f[x][j]表示x子树中从x往下延伸的深度为j的链上的最大点权和，设c[x][j]表示满足上述条件的链的条数，合并轻儿子时用轻儿子和重儿子的信息更新答案，再用轻儿子的信息更新重儿子的信息，最后用重链上的信息更新一下答案。

但是我们发现在一个点i继承其重儿子q[x]的信息时，需要对f[x][]中的每一个数加上q[x]的点权，而直接这样做是O(n)的，那我们长链剖分的复杂度就会掉到O(n^2)，和暴力没区别。于是考虑优化。

开一个标记数组w[x]（可以直接用记录点权的数组，我就是这样写的），表示在处理f[x][]数组时，里面每一个数的实际值都是记录在数组里的值加上w[i]的结果。转移标记就是w[x]+=w[q[x]]。在合并轻儿子时，用f[x][K-j]+f[y][j]+w[q[x]]+w[y]来更新答案（q[x]是重儿子，K的值是题目所给的值-2（至于为什么，可以自己手玩），y是轻儿子），这样就统计了跨过点x的答案，然后用f[y][j]+w[y]-w[q[x]]来更新f[x][j+1]的信息，再用f[x][K+1]+w[q[x]]来统计一下重链上的答案就好了。但是要注意每个f[x][0]=-w[q[x]]，这样是为了方便转移。从我的描述中就可以看到，我们打的标记并不会对复杂度产生影响，仍是优秀的O(n)。

实现起来就是细节有点多，打的时候注意。（f[x][j]和c[x][j]是用结构体记的） 

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define R register
#define I inline
#define P push_back
#define M make_pair
#define O first
#define T second
using namespace std;
const int S=30003;
char buf[S],*p1,*p2;
I char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,S,stdin),p1==p2)?EOF:*p1++;}
I int rd(){
    R int f=0; R char c=gc();
    while(c<48||c>57) c=gc();
    while(c>47&&c<58) f=f*10+(c^48),c=gc();
    return f;
}
struct N{int f,c;N(){f=0,c=1;}}u[S],*f[S],*e=u+1;
int h[S],s[S],g[S],b[S],k[S],d[S],t[S],p[S],q[S],w[S],c,o,l,K;
vector<pair<int,int> > v[S]; priority_queue<pair<int,int> > Q;
I int max(int x,int y){return x>y?x:y;}
I void add(int x,int y){s[++c]=h[x],h[x]=c,g[c]=y,b[y]=1,p[y]=x;}
void dfs0(int x){
    for(R int i=0,y,z,m=v[x].size();i<m;++i)
        if(!b[y=v[x][i].O]&&k[x]+(z=v[x][i].T)==k[y]) add(x,y),w[y]=z,dfs0(y);
}
void dfs1(int x){t[x]=d[x]=d[p[x]]+1;
    for(R int i=h[x],y;i;i=s[i])
        if((y=g[i])^p[x]){dfs1(y);
            if(t[y]>t[x]) t[x]=t[y],q[x]=y;
        }
}
void dfs2(int x){f[x][0].c=1;
    R int i,j,y,z,u,v,m; if(!q[x]) return ;
    f[q[x]]=f[x]+1,dfs2(q[x]),w[x]+=(v=w[q[x]]),f[x][0].f-=v;
    for(i=h[x];i;i=s[i])
        if((y=g[i])^p[x]&&y^q[x]){f[y]=e,m=t[y]-d[y]+1,e+=m,dfs2(y),u=w[y];
            for(j=max(K-t[x]+d[x],0);j<m&&K-j;++j)
                if((z=f[y][j].f+f[x][K-j].f+u+v)>o) o=z,l=f[y][j].c*f[x][K-j].c;
                else if(o==z) l+=f[x][K-j].c*f[y][j].c;
            for(j=0;j<m;++j)
                if((z=f[y][j].f+u-v)>f[x][j+1].f)
                    f[x][j+1].f=z,f[x][j+1].c=f[y][j].c;
                else if(z==f[x][j+1].f) f[x][j+1].c+=f[y][j].c;
        }
    if(K+1>t[x]-d[x]+1) return ;
    if((z=f[x][K+1].f+v)>o) o=z,l=f[x][K+1].c; else if(o==z) l+=f[x][K+1].c;
}
int main(){
    R int n=rd(),m=rd(),i,x,y,z;
    for(K=rd()-2,i=1;i<=m;++i) x=rd(),y=rd(),z=rd(),v[x].P(M(y,z)),v[y].P(M(x,z));
    for(i=1;i<=n;++i) sort(v[i].begin(),v[i].end());
    memset(k,0x3f,sizeof k),k[1]=0,Q.push(M(0,1));
    while(!Q.empty()){x=Q.top().T,Q.pop();
        if(b[x]) continue; b[x]=1;
        for(i=0,m=v[x].size();i<m;++i)
            if(k[y=v[x][i].O]>k[x]+(z=v[x][i].T))
                k[y]=k[x]+z,Q.push(M(-k[y],y));
    }
    memset(b,0,sizeof b),dfs0(1),dfs1(1),f[1]=e,e+=t[1],dfs2(1);
    printf("%d %d",o,l);
    return 0;
}

本来以为可以复杂度踩点分治，仔细一看才想起dij的复杂度是O(nlogn)的，总的复杂度还是nlogn，只能夸夸自己常数小了。