hdu 4871 樹的分治+最短路記錄路徑
/*
題意：給你一些節點和一些邊，求最短路徑樹上是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];
queueq;
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(titmxx) {
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
