主要考察知识：点分治+最短路径生成树。
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
",ans,num);
return 0;
}
深深地感到自己的弱小。