题目大意：略 传送门
硬是把两个题拼到了一起= =
$dijkstra$搜出单源最短路，然后$dfs$建树，如果$dis_{v}=dis_{u}+e.val$，说明这条边在最短路图内，然后像$NOIP2018 D2T1$那样的思路，贪心地选出当前节点的所有子节点里，未被访问过的编号最小的节点递归，回溯后重复此过程。可以用$vector$预处理出来，或者用堆= =。
然后就是很经典的点分治问题了
求出树上固定边数的最长链，类似于[IOI2011]Race这道题的思路，只不过是反着搞。每次选择一个重心为根，开个桶统计答案就行了
求固定长度链的个数。但这道题用桶可能会存不下，可以写$map$代替桶(不过数据里好像没有存不下的情况..)。
由于判定条件是二元的，一个是边数一个是长度，排序双指针不知道行不行
还有我把$vector$改成堆就过了是什么鬼
代码巨长巨恶心
#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 30010
#define M1 1010
#define ll long long
#define inf 233333333
#define it map<node,int>::iterator
using namespace std; int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
}
int n,m,K;
struct Edge{
int to[N1<<],nxt[N1<<],val[N1<<],head[N1],cte;
void ae(int u,int v,int w)
{
cte++;to[cte]=v,val[cte]=w;
nxt[cte]=head[u],head[u]=cte;
}
}g,e;
namespace Build_Tree{
struct node{
int id,val;
friend bool operator < (const node &s1,const node &s2){
if(s1.val!=s2.val) return s1.val>s2.val;
return s1.id>s2.id;
}
};
int cmp(node s1,node s2){return s1.id<s2.id;}
int vis[N1],dis[N1];
void dijkstra()
{
memset(dis,0x3f,sizeof(dis));
priority_queue<node>q;
q.push((node){,}); dis[]=;
int j,u,v; node k;
while(!q.empty())
{
k=q.top(); q.pop(); u=k.id; if(vis[u]) continue; vis[u]=;
for(j=g.head[u];j;j=g.nxt[j])
{
v=g.to[j];
if(dis[v]>dis[u]+g.val[j])
dis[v]=dis[u]+g.val[j], q.push((node){v,dis[v]});
}
}
memset(vis,,sizeof(vis));
}
priority_queue<node>q[N1];
void dfs(int u)
{
vis[u]=; node k;
for(int j=g.head[u];j;j=g.nxt[j])
{
if(vis[g.to[j]]||dis[g.to[j]]!=dis[u]+g.val[j]) continue;
q[u].push((node){g.val[j],g.to[j]});
}
while(!q[u].empty())
{
k=q[u].top(); q[u].pop(); if(vis[k.val]) continue;
e.ae(u,k.val,k.id); e.ae(k.val,u,k.id);
dfs(k.val);
}
}
void Main()
{
dijkstra();
dfs();
}
};
int sz[N1],ms[N1],use[N1],tsz,G;
void gra(int u,int dad)
{
sz[u]=; ms[u]=;
for(int j=e.head[u];j;j=e.nxt[j])
{
if(use[e.to[j]]||e.to[j]==dad) continue;
gra(e.to[j],u);
sz[u]+=sz[e.to[j]]; ms[u]=max(ms[u],sz[e.to[j]]);
}
ms[u]=max(ms[u],tsz-sz[u]);
if(ms[u]<ms[G]) G=u;
} int ma[N1],q[N1],eq,tq[N1],et,dep[N1],dis[N1]; namespace Find_ma{
int ans;
void dfs(int u,int dad)
{
if(dep[u]>K) return; tq[++et]=u;
for(int j=e.head[u];j;j=e.nxt[j])
{
if(use[e.to[j]]||e.to[j]==dad) continue;
dep[e.to[j]]=dep[u]+; dis[e.to[j]]=dis[u]+e.val[j];
dfs(e.to[j],u);
}
}
void calc(int u)
{
int i,j,x;
dep[u]=; ma[]=;
for(j=e.head[u];j;j=e.nxt[j])
{
if(use[e.to[j]]) continue;
dep[e.to[j]]=; dis[e.to[j]]=e.val[j];
dfs(e.to[j],u);
for(i=;i<=et;i++)
{
x=tq[i];
ans=max(ans,ma[K-dep[x]]+dis[x]);
}
while(et)
{
x=tq[et--]; q[++eq]=dep[x];
ma[dep[x]]=max(ma[dep[x]],dis[x]);
}
}
while(eq) ma[q[eq--]]=-inf;
}
void main_dfs(int u)
{
int j,v; use[u]=; calc(u);
for(j=e.head[u];j;j=e.nxt[j])
{
v=e.to[j]; if(use[v]) continue;
tsz=sz[v]; G=; gra(v,u);
main_dfs(G);
}
}
void solve()
{
ms[]=tsz=n; G=; gra(,-); gra(G,-);
for(int i=;i<=n;i++) ma[i]=-inf;
main_dfs(G);
}
}; namespace Count{ struct node{
int dis,dep;
friend bool operator < (const node &s1,const node &s2)
{
if(s1.dis!=s2.dis) return s1.dis<s2.dis;
return s1.dep<s2.dep;
}
};
int M,ans; map<node,int>mp;
void dfs(int u,int dad)
{
if(dis[u]>M||dep[u]>K) return;
mp[(node){dis[u],dep[u]}]++;
for(int j=e.head[u];j;j=e.nxt[j])
{
if(use[e.to[j]]||e.to[j]==dad) continue;
dep[e.to[j]]=dep[u]+; dis[e.to[j]]=dis[u]+e.val[j];
dfs(e.to[j],u);
}
}
int calc(int u)
{
int ret=; node k,t; mp.clear(); dfs(u,-);
for(it i=mp.begin();i!=mp.end();i++)
{
k=i->first; t=(node){M-k.dis,K-k.dep};
if(mp.find(t)==mp.end()) continue;
if(k.dis==t.dis&&k.dep==t.dep) ret+=(i->second)*((i->second)-);
else ret+=mp[t]*(i->second);
}
return ret/;
}
void main_dfs(int u)
{
int j,v; use[u]=; dis[u]=; dep[u]=; ans+=calc(u);
for(j=e.head[u];j;j=e.nxt[j])
{
v=e.to[j]; if(use[v]) continue;
ans-=calc(v); tsz=sz[v]; G=; gra(v,u);
main_dfs(G);
}
}
void solve()
{
M=Find_ma::ans;
memset(use,,sizeof(use));
ms[]=tsz=n; G=; gra(,-); gra(G,-);
main_dfs(G);
}
}; int main()
{
//freopen("t2.in","r",stdin);
int i,x,y,z;
scanf("%d%d%d",&n,&m,&K); K--;
for(i=;i<=m;i++)
{
x=gint(),y=gint(),z=gint();
g.ae(x,y,z),g.ae(y,x,z);
}
Build_Tree::Main();
Find_ma::solve();
Count::solve();
printf("%d %d\n",Find_ma::ans,Count::ans);
return ;
}
/*
6 6 4
1 2 1
2 3 1
3 4 1
2 5 1
3 6 1
5 6 1 3 4 7 6 4
1 2 2
1 3 1
2 4 4
2 5 3
3 6 2
5 7 2 9 1
*/