题目
给定一个无向图，求出其最短路径树上面的，包含 (k) 个点的一条路径，使得这条路径权值尽可能大，并求出有多少条长度为这个的路径（不要求为 (k) 个点）。
分析
没意思题，点分治+最短路。
先直接跑最短路后建出树来。
然后如果把点数当作边权，把路径权值当作价值，题目就相当于是P4149 [IOI2011]Race求最大值了。
然后求出最大值后，考虑统计答案，相当于就是统计树上距离为 (D) 的点对个数，模板。
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)) f|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;return;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return;
}
const int N=2e5+5,INF=1e9+7;
int n,m,k;
int head[N],nex[N],to[N],w[N],idx;
int dis[N],vis[N],pre[N],val[N];
int t[N],Vis[N],t1[N],tot[N],tmp;
int Ans,Num,Root,Max,Size,siz[N],son[N];
inline void add(int x,int y,int z){idx++;nex[idx]=head[x];head[x]=idx;to[idx]=y;w[idx]=z;}
priority_queue<pair<int,int> >q;
inline void GetRoot(int x,int fa){
siz[x]=1;son[x]=0;
for(int i=head[x];i;i=nex[i]){
int t=to[i];
if(t==fa||vis[t])continue;
GetRoot(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(Max>son[x])Max=son[x],Root=x;
return ;
}
inline void Calc(int x,int fa,int dist,int dep){
if(t1[dep]<dist) t1[dep]=dist,tot[dep]=1;
else if(t1[dep]==dist) tot[dep]++;
if(dep>tmp)tmp=dep;
for(int i=head[x];i;i=nex[i]){
int t=to[i];
if(t==fa||vis[t])continue;
Calc(t,x,dist+w[i],dep+1);
}
return ;
}
inline void DFS(int x){
Vis[0]=vis[x]=true;
int dep=0;
for(int i=head[x];i;i=nex[i]){
int y=to[i];tmp=0;
if(vis[y])continue;
Calc(y,x,w[i],1);
if(tmp>dep) dep=tmp;
for(int j=1;j<=tmp;j++){
if(Vis[k-1-j]){
if(Ans<t1[j]+t[k-1-j]) Ans=t1[j]+t[k-1-j],Num=tot[j]*Vis[k-1-j];
else if(Ans==t1[j]+t[k-1-j]) Num+=tot[j]*Vis[k-1-j];
}
}
for(int j=1;j<=tmp;j++){
if(t1[j]>t[j]) t[j]=t1[j],Vis[j]=tot[j];
else if(t1[j]==t[j]) Vis[j]+=tot[j];
}
for(int j=1;j<=tmp;j++) t1[j]=tot[j]=0;
}
for(int i=0;i<=dep;i++) t[i]=Vis[i]=0;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(vis[y])continue;
Root=0,Max=INF,Size=siz[y];
GetRoot(y,x);
DFS(Root);
}
return ;
}
void Dijkstra(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;q.push(make_pair(0,1));
while(!q.empty()){
int x=q.top().second;q.pop();
if(vis[x]) continue;
vis[x]=true;
for(int i=head[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];
}
}
idx=0;memset(head,0,sizeof(head));
for(int i=2;i<=n;i++) add(i,pre[i],val[i]),add(pre[i],i,val[i]);
return ;
}
int main(){
read(n),read(m),read(k);
for(int i=1;i<=m;i++){
int x,y,z;
read(x),read(y),read(z);
add(x,y,z),add(y,x,z);
}
Dijkstra();
Max=INF,Size=n,Root=0;
memset(vis,0,sizeof(vis));
GetRoot(1,0);
DFS(Root);
write(Ans),putchar(' '),write(Num);
return 0;
}