题目链接：
题解：
我就是个智障。明明是道大水题，硬是拖了6h。
关于这道题我唯一想说的就是，记得更新拆分后的子树大小！！！我就是ZZ恒（QwQ。
代码：
#define Troy 10/26/2017
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int s=,k=;char ch=getchar();
while(ch<''|ch>'') ch=='-'?k=-:,ch=getchar();
while(ch>&ch<='') s=s*+(ch^),ch=getchar();
return s*k;
}
const int N=3e5+;
int n,m,K;
struct edges{
int v,w;edges *last;
}edge[N<<],*head[N];int cnt;
inline void push(int u,int v,int w){
edge[++cnt]=(edges){v,w,head[u]};head[u]=edge+cnt;
}
int q[N],dis[N],from[N];
bool vis[N];
inline void dfs(int x){
vis[x]=true;
vector<int > G;
for(edges *i=head[x];i;i=i->last) if(!vis[i->v]&&dis[i->v]==dis[x]+i->w)
G.push_back(i->v);
sort(G.begin(),G.end());
for(int i=;i<G.size();i++){
if(vis[G[i]]) continue;
dfs(G[i]);
from[G[i]]=x;
}
}
inline void spfa(){
int l=,r=;
q[]=;
memset(dis,,sizeof(dis));
dis[]=;
while(l!=r){
int x=q[l++];if(l==N) l=;
for(edges *i=head[x];i;i=i->last){
if(dis[x]+i->w<dis[i->v]){
dis[i->v]=dis[x]+i->w;
if(!vis[i->v])
vis[i->v]=true,q[r++]=i->v;
if(r==N) r=;
}
}
vis[x]=false;
}
dfs();
}
int heavy[N],root,size[N],tot,top,ans=,sum,T[N],t[N],clocks,cnts[N];
inline void dfs(int x,int fa){
size[x]=,heavy[x]=;
for(edges *i=head[x];i;i=i->last)if(i->v!=fa&&(!vis[i->v])){
dfs(i->v,x);
size[x]+=size[i->v];
heavy[x]=max(heavy[x],size[i->v]);
}
heavy[x]=max(heavy[x],tot-size[x]);
if(heavy[x]<=top)
top=heavy[x],root=x;
}
struct node{
int v,w;
inline friend bool operator <(node x,node y){
return size[x.v]<size[y.v];
}
}sons[N];
inline void calc(int x,int fa,int w,int deep){
if(T[K-deep]==clocks){
if(ans<t[K-deep]+w)
ans=t[K-deep]+w,sum=;
if(ans==t[K-deep]+w)
sum+=cnts[K-deep];
}
if(deep+<K)
for(edges *i=head[x];i;i=i->last) if(i->v!=fa&&vis[i->v]==){
calc(i->v,x,w+i->w,deep+);
}
}
inline void update(int x,int fa,int w,int deep){
if(T[deep]==clocks){
if(t[deep]<w)
t[deep]=w,cnts[deep]=;
if(t[deep]==w)
cnts[deep]++;
}
else T[deep]=clocks,t[deep]=w,cnts[deep]=;
if(deep<K)
for(edges *i=head[x];i;i=i->last) if(i->v!=fa&&vis[i->v]==){
update(i->v,x,w+i->w,deep+);
}
}
inline void solve(int x){
clocks++;
top=0x7fffffff;
dfs(x,x);
vis[root]=true;
x=root;
int num();
T[]=clocks;
for(edges *i=head[x];i;i=i->last)if(vis[i->v]^){
sons[++num]=(node){i->v,i->w};
}
sort(sons+,sons++num);
for(int i=;i<=num;i++){
calc(sons[i].v,x,sons[i].w,);
if(i<num)
update(sons[i].v,x,sons[i].w,);
}
for(edges *i=head[x];i;i=i->last) if(vis[i->v]^)
if(size[i->v]>=K){
tot=size[i->v],solve(i->v);
}
}
int main(){
n=read(),m=read(),K=read();
for(int i=,u,v,w;i<=m;i++){
u=read(),v=read(),w=read();
push(u,v,w);push(v,u,w);
}
spfa();
memset(vis,,sizeof(vis));
memset(head,,sizeof(head));
cnt=;
for(int i=;i<=n;i++)
push(from[i],i,dis[i]-dis[from[i]]),
push(i,from[i],dis[i]-dis[from[i]]);
tot=n;
cnts[]=;
solve();
printf("%d %d\n",ans,sum);
}