LINK：最短路径树问题
这道题要求出 最短路径树 字典序得最小。在这棵树上要求出包含K个点的最长路径长度 和 包含K个点的最长路径长度的路径有多少条。
最短路径树一般我们求出最短路后 在最短路图上dfs一遍 以dfs树作为最短路径树。
要求字典序最小 常规方法 开vector存图 sort一下 然后再dfs。
求包含K个点的最长路径长度 可以树形dp 不过考虑到换根的时候复杂度过高。
对于路径问题上点分治 发现很容易求出。
而对于包含K个点的我们可以在求上一问的时候顺便求出。
所以这道题考的其实是dfs树+点分治。
const int MAXN=60010;
int n,m,k,len,root,ans,maxx,mx;
vector<int>G[MAXN];ll sum;
int dis[MAXN],vis[MAXN],son[MAXN],sz[MAXN],g[MAXN],f[MAXN],sg[MAXN],sf[MAXN];
int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1],e[MAXN<<1];
priority_queue<pii>q;
inline void add(int x,int y,int z)
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
e[len]=z;
}
inline void dij()
{
memset(dis,0x3f,sizeof(dis));
dis[1]=0;q.push(mk(-dis[1],1));
while(q.size())
{
int x=q.top().S;q.pop();
if(vis[x])continue;
vis[x]=1;
go(x)
{
if(dis[tn]>dis[x]+e[i])
{
dis[tn]=dis[x]+e[i];
q.push(mk(-dis[tn],tn));
}
}
}
}
inline void dfs(int x)
{
vis[x]=1;
sort(G[x].begin(),G[x].end());
if(!G[x].size())return;
rep(0,G[x].size()-1,i)
{
int tn=G[x][i];
if(vis[tn])continue;
add(x,tn,dis[tn]-dis[x]);
add(tn,x,dis[tn]-dis[x]);
dfs(tn);
}
}
inline void get_root(int x,int father)
{
sz[x]=1;son[x]=0;
go(x)
{
if(tn==father||vis[tn])continue;
get_root(tn,x);
sz[x]+=sz[tn];
son[x]=max(son[x],sz[tn]);
}
son[x]=max(son[x],maxx-sz[x]);
if(son[root]>son[x])root=x;
}
inline void get_dis(int x,int father,int dis,int d)
{
if(dis==f[d])++sf[d];
if(dis>f[d])f[d]=dis,sf[d]=1;
mx=max(mx,d);
go(x)
{
if(tn==father||vis[tn])continue;
get_dis(tn,x,dis+e[i],d+1);
}
}
inline void solve(int x)
{
vis[x]=1;
g[1]=0;sg[1]=1;
int w1=0,w2=maxx;
go(x)
{
if(vis[tn])continue;
mx=0;get_dis(tn,0,e[i],2);
w1=max(w1,mx);
rep(2,min(k,mx),j)
{
if(f[j]+g[k-j+1]==ans)sum+=(ll)sf[j]*sg[k-j+1];
if(f[j]+g[k-j+1]>ans)ans=f[j]+g[k-j+1],sum=(ll)sf[j]*sg[k-j+1];
}
rep(2,mx,j)
{
if(f[j]>g[j])g[j]=f[j],sg[j]=sf[j];
else if(f[j]==g[j])sg[j]+=sf[j];f[j]=sf[j]=0;
}
}
rep(1,w1,i)g[i]=sg[i]=0;
go(x)
{
if(vis[tn])continue;
root=0;maxx=sz[tn]>sz[x]?w2-sz[x]:sz[tn];
get_root(tn,0);solve(root);
}
}
int main()
{
freopen("1.in","r",stdin);
get(n);get(m);get(k);
rep(1,m,i)
{
int x,y,z;
get(x);get(y);get(z);
add(x,y,z);add(y,x,z);
}
dij();len=0;
rep(1,n,j)go(j)if(dis[tn]==dis[j]+e[i])G[j].pb(tn);
rep(1,n,i)lin[i]=vis[i]=0;
dfs(1);memset(vis,0,sizeof(vis));
son[0]=maxx=n;get_root(1,0);solve(root);
printf("%d %lld
",ans,sum);
return 0;
}
注意g 和 f数组的更新不要出错。