Description
给一个包含n个点，m条边的无向连通图。从顶点1出发，往其余所有点分别走一次并返回。
往某一个点走时，选择总长度最短的路径走。若有多条长度最短的路径，则选择经过的顶点序列字典序最小的那条路径(如路径A为1,32,11，路径B为1,3,2,11，路径B字典序较小。注意是序列的字典序的最小，而非路径中节点编号相连的字符串字典序最小)。到达该点后按原路返回，然后往其他点走，直到所有点都走过。
可以知道，经过的边会构成一棵最短路径树。请问，在这棵最短路径树上，最长的包含K个点的简单路径长度为多长？长度为该最长长度的不同路径有多少条？
这里的简单路径是指：对于一个点最多只经过一次的路径。不同路径是指路径两端端点至少有一个不同，点A到点B的路径和点B到点A视为同一条路径。
solution
正解：点分治
构出最短路图，在最短路图上面尽量走编号小的点，直到所有的点都加入集合中，构成了最短路树
然后点分治即可
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
#include <vector>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=30005,inf=2e8;
int n,m,k,Head[N],nxt[N*10],to[N*10],dis[N*10],num=1,head[N];
inline void link1(int x,int y,int z){
nxt[++num]=Head[x];to[num]=y;dis[num]=z;Head[x]=num;}
inline void link2(int x,int y,int z){
nxt[++num]=head[x];to[num]=y;dis[num]=z;head[x]=num;}
bool v[N],d[N];int dd[N];
inline void spfa(int S){
queue<int>q;while(!q.empty())q.pop();
for(RG int i=0;i<=n;i++)dd[i]=inf,v[i]=0;
q.push(S);dd[S]=0;v[S]=1;
int x,u;
while(!q.empty()){
x=q.front();q.pop();
for(RG int i=Head[x];i;i=nxt[i]){
u=to[i];
if(dd[x]+dis[i]<dd[u]){
dd[u]=dd[x]+dis[i];
if(!v[u])v[u]=1,q.push(u);
}
}
v[x]=0;
}
}
struct Grath{int x,dis,id;
bool operator <(const Grath &pr)const{return x<pr.x;}};
vector<Grath>G[N];
struct edge{int x,y,z;}e[N*10];
int root=0,son[N]={N},sz[N],sum;bool vis[N];
inline void getroot(int x,int last){
sz[x]=1;son[x]=0;
for(int i=head[x];i;i=nxt[i]){
int u=to[i];
if(vis[u] || u==last)continue;
getroot(u,x);
sz[x]+=sz[u];
if(sz[u]>son[x])son[x]=sz[u];
}
son[x]=Max(son[x],sum-sz[x]);
if(son[x]<son[root])root=x;
}
int g[N],f[N],de[N],den=0;bool inde[N];
inline void upd(int x,int last,int dist,int l){
if(l>k)return ;
if(dist>f[l]){
f[l]=dist,g[l]=1;
if(!inde[l])inde[l]=true,de[++den]=l;
}
else if(dist==f[l])g[l]++;
for(int i=head[x];i;i=nxt[i]){
int u=to[i];
if(vis[u] || u==last)continue;
upd(u,x,dist+dis[i],l+1);
}
}
int ans=0,cnt=0;
inline void getdis(int x,int last,int dist,int l){
if(l>k)return ;
if(dist+f[k-l]>ans)ans=dist+f[k-l],cnt=g[k-l];
else if(dist+f[k-l]==ans)cnt+=g[k-l];
for(int i=head[x];i;i=nxt[i]){
int u=to[i];
if(vis[u] || u==last)continue;
getdis(u,x,dist+dis[i],l+1);
}
}
inline void calc(int x){
g[0]=1;
for(int i=head[x];i;i=nxt[i]){
int u=to[i];if(vis[u])continue;
getdis(u,x,dis[i],2);upd(u,x,dis[i],1);
}
while(den)f[de[den]]=0,g[de[den]]=0,inde[de[den]]=0,den--;
}
inline void solve(int x){
vis[x]=1;calc(x);
for(int i=head[x];i;i=nxt[i]){
int u=to[i];
if(vis[u])continue;
root=0;sum=sz[u];getroot(u,x);
solve(root);
}
}
bool b[N];
inline void dfs(int x){
b[x]=1;
for(RG int i=0,sz=G[x].size();i<sz;i++){
int u=G[x][i].x,id=G[x][i].id;
if(dd[x]+G[x][i].dis==dd[u] && !b[u]){
link2(e[id].x,e[id].y,e[id].z);
link2(e[id].y,e[id].x,e[id].z);
dfs(u);
}
}
}
void work()
{
int x,y,z;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
e[i].x=x;e[i].y=y;e[i].z=z;
link1(x,y,z);link1(y,x,z);
G[x].push_back((Grath){y,z,i});
G[y].push_back((Grath){x,z,i});
}
for(int i=1;i<=n;i++)sort(G[i].begin(),G[i].end());
spfa(1);dfs(1);
sum=n;root=0;getroot(1,1);
solve(root);
printf("%d %d
",ans,cnt);
}
int main()
{
work();
return 0;
}