先用dijkstra把最短路树建出来，然后就是树的质心分治了。
经过k个点的路径，要么全在子树上，要么经过根结点，因此可以分治。
如果分治的时候选点不好会变成O(n^2)，比较极端的情况是比如树是一条链。
选择质心可以保证最大子树结点不超过n/2，每次递归至少减半，递归层数是O(logn)的。
找子树质心是O(n)的树形dp，枚举到根结点的路径是O(n)的。
把经过根节点并且路径上有c个结点的最长路径以及方案保存到一个map，对于一条新增的路径去查找k-c个点的路径，就可以更新答案了。
如果用的unorder_map，那么查找是O(1)的，因此分治复杂度是T(n) = 2*T(n/2) + O(n) ≈ O(nlogn)。
总体复杂度是O(mlogn + nlogn)
/********************************************************* * ------------------ * * author AbyssFish * **********************************************************/ #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<queue> #include<vector> #include<stack> #include<map> #include<set> #include<algorithm> #include<cmath> #include<numeric> #include<climits> #include<unordered_map> using namespace std; const int maxn = 30000+2; const int maxm = 60000*2+3; typedef long long ll; #define sInt 4 int hd[maxn], nx[maxm], to[maxm], we[maxm], ec; #define eachedge int i = hd[u]; ~i; i = nx[i] void init_g(int n){ memset(hd+1,0xff,sInt*n); ec = 0; } void add_edge(int u,int v,int c) { to[ec] = v; we[ec] = c; nx[ec] = hd[u]; hd[u] = ec++; } int n,m,k; int di[maxn], fe[maxn]; typedef pair<int,int> pii; #define dist first #define ver second priority_queue<pii,vector<pii>,greater<pii> > q; void dijkstra() { memset(di+1,0x3f,sInt*n); di[1] = 0; fe[1] = -1; q.push(pii(0,1)); while(!q.empty()){ pii x = q.top(); q.pop(); if(x.dist != di[x.ver]) continue; int u = x.ver; for(int i = hd[u]; ~i; i = nx[i]){ int v = to[i]; if(di[v] > di[u] + we[i]){ di[v] = di[u]+we[i]; fe[v] = i; q.push(pii(di[v],v)); } else if(di[v] == di[u] + we[i] && to[fe[v]^1] > u){ fe[v] = i; } } } } void rewrite(int u,int i) { nx[i] = hd[u]; hd[u] = i; } void build_tree() { dijkstra(); init_g(n); for(int v = 2; v <= n; v++){ int e = fe[v]; int u = to[e^1]; rewrite(u,e); rewrite(v,e^1); } } bool vis_c[maxn]; int tr_sz[maxn]; void cal_tr_sz(int u,int f) { int &c = tr_sz[u]; c = 1; for(eachedge){ int v = to[i]; if(v == f || vis_c[v]) continue; c += tr_sz[v]; cal_tr_sz(v,u); } } int block_size; int best, centroid; void findCentroid(int u,int f) { int mx = 0; for(eachedge){ int v = to[i]; if(v == f || vis_c[v]) continue; findCentroid(v,u); mx = max(mx, tr_sz[v]); } mx = max(mx,block_size-tr_sz[u]); if(best > mx){ best = mx; centroid = u; } } typedef unordered_map<int,pii> cont; typedef cont::iterator con_it; //key 经过的点数，value(最长距离,方案数) cont prv; cont tmp; void update(cont &res,int c, const pii &np) { con_it it = res.find(c); if(it != res.end()){ pii &p = it->second; if(p.dist == np.dist) p.ver += np.ver; else if(p.dist < np.dist) { p = np; } } else { res.insert(make_pair(c,np)); } } void enum_path(int u,int f,int c,int d,cont &res) { if(c >= k) return; update(res,c,pii(d,1)); for(eachedge){ int v = to[i]; if(v == f || vis_c[v]) continue; enum_path(v,u,c+1,d+we[i],res); } } int ans; ll cnt; void divide(int rt) { cal_tr_sz(rt,-1); best = INT_MAX; block_size = tr_sz[rt]; findCentroid(rt,-1); int u = centroid; vis_c[u] = true; for(eachedge){ if(!vis_c[to[i]]) divide(to[i]); } prv.clear(); prv.insert(make_pair(1,pii(0,1))); for(eachedge){ if(vis_c[to[i]]) continue; tmp.clear(); enum_path(to[i],u,1,we[i],tmp); con_it it, it2; for(it = tmp.begin(); it != tmp.end(); it++){ int c = it->first; pii &p = it->second; if((it2 = prv.find(k-c)) != prv.end()){ ll dis = it2->second.dist + p.dist; if(dis > ans){ ans = dis; cnt = p.ver * it2->second.ver; } else if(dis == ans) cnt += p.ver * it2->second.ver; } } for(it = tmp.begin(); it != tmp.end(); it++){ int c = it->first+1; update(prv,c,it->second); } } vis_c[u] = false; } void solve() { build_tree(); ans = cnt = 0; divide(1); printf("%d %lld ",ans,cnt); } void init() { scanf("%d%d%d",&n,&m,&k); init_g(n); for(int i = 0; i < m; i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add_edge(a,b,c); add_edge(b,a,c); } } //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif int T; scanf("%d",&T); while(T--){ init(); solve(); } return 0; }