/*
题意：给你一些节点和一些边，求最短路径树上是k个节点的最长的路径数。
解：1、求出最短路径树--spfa加记录
2、树上进行操作--树的分治，分别处理子树进行补集等运算
*/
#include
#include
#include
#include
#include
#include
#define ll __int64 using namespace std; #define N 31000 #define inf 10000000000000000 ll kk; struct node { ll u,v,w,next; }bian[N*4]; ll yong,head[N]; void init() { yong=0; memset(head,-1,sizeof(head)); } void addedge(ll u,ll v,ll w) { bian[yong].u=u; bian[yong].v=v; bian[yong].w=w; bian[yong].next=head[u]; head[u]=yong++; } ll Min(ll v,ll vv) { return v>vv?vv:v; } ll premi[N],val[N];//用来记录前一个元素的字典序最小和前一条边的权值 void spfa(ll u,ll n) { ll i,cur,dis[N],vis[N]; queue
q; for(i=1;i<=n;i++) dis[i]=inf; memset(vis,0,sizeof(vis)); memset(premi,-1,sizeof(premi)); dis[u]=0; q.push(u); while(!q.empty()) { cur=q.front(); q.pop(); vis[cur]=0; for(i=head[cur];i!=-1;i=bian[i].next) { ll v=bian[i].v; if(dis[v]>dis[cur]+bian[i].w) { dis[v]=dis[cur]+bian[i].w; val[v]=bian[i].w; premi[v]=cur;//记录前一个节点 if(!vis[v]) { vis[v]=1; q.push(v); } } else if(dis[v]==dis[cur]+bian[i].w) { if(premi[v]==-1)premi[v]=cur; else premi[v]=Min(premi[v],cur); } } } return ; } /*以下是树的分治部分*/ ll minn,ma,num[N],nn,diss[N],len,mxx,mxnum,vis[N],ed[N]; void dfs1(ll u,ll fa) { ll i; nn++; for(i=head[u];i!=-1;i=bian[i].next) { ll v=bian[i].v; if(v!=fa&&!vis[v]) dfs1(v,u); } return ; } ll Max(ll v,ll vv) { return v>vv?v:vv; } void dfs2(ll u,ll fa) { num[u]=1; ll i,tit=0; for(i=head[u];i!=-1;i=bian[i].next) { ll v=bian[i].v; if(v!=fa&&!vis[v]) { dfs2(v,u); num[u]+=num[v]; tit=Max(tit,num[v]); } } tit=Max(tit,nn-num[u]); if(tit
mxx) { mxx=diss[j]; mxnum=1; } else if(diss[j]==mxx) mxnum++; } if(kk-ed[j]-1<=0)continue; k=diss[j]+f[kk-ed[j]].dis;//补集 // printf("khe=%I64d\n",k); if(k>mxx) { mxx=k; mxnum=f[kk-ed[j]].num; } else if(k==mxx) mxnum+=f[kk-ed[j]].num; } for(j=1;j<=len;j++) {//加入补集 if(ed[j]+1>=kk)continue; if(f[ed[j]+1].dis