题解 P2993 【[FJOI2014]最短路径树问题】
watermonster · · 题解
很裸的一道点分治，感觉就是这道题的升级版。
显然我们就是要建出最短路径树，然后直接在树上跑点分治就行了。
首先，关于建树
题目要求我们按字典序最小的路径建树，但由于官方数据过水，貌似大部分题解都没管字典序(不过后来添加了hack数据)。我们可以用一个贪心思想来建树：首先通过dfs来建树，将以当前点为起点的在最短路上且儿子不在树上的边加到树上，然后对所有在树上连了边的子节点继续dfs，在这里我们可以贪心地按编号从小到大作为顺序来搜索。因为对于后面的一个子孙节点来说，当前点的子节点在字典序上的位权一定是一样的。就像题干中给出的1,32,11和1,3,2,11。因为无论后面的路径长短，前面部分的路径一定是一样的。比如1的儿子有32和3，此时32和3之间我们就应该选编号较小的3。
建树部分代码：
struct tmp{int v,w;bool operator <(const tmp&x)const{return v<x.v;}};
void build(int x)
{
vector<tmp>son;
for(re int i=h[x];i;i=e[i].nxt)
if(dis[e[i].v]==dis[x]+e[i].w)
son.push_back((tmp){e[i].v,e[i].w});//将儿子加入vector中方便排序
sort(son.begin(),son.end());//按编号从小到大排序
for(re int i=0;i<son.size();++i)
if(!ontree[son[i].v])//当前儿子不在树上
{
ontree[son[i].v]=true;
divide::add(x,son[i].v,son[i].w);
divide::add(son[i].v,x,son[i].w);//加边
build(son[i].v);//继续建树
}
}当建好树之后，我们就可以考虑如何统计答案了。
问题：
请问，在这棵最短路径树上，最长的包含K个点的简单路径长度为多长？长度为该最长长度的不同路径有多少条？
对于最长路径的长度，做法可以参考这里。我们可以开两个栈，一个存链长，一个存深度，若当前链经过节点数为
点分治部分代码：
namespace divide
{
int cnt,h[N];
struct edge{int v,w,nxt;}e[N<<1];
il void add(int u,int v,int w){e[++cnt]=(edge){v,w,h[u]};h[u]=cnt;}
int rt,sum;
int siz[N],son[N],dis[N],dep[N],len[N],tot[N];
//len[i]表示经过i个点的最长链长度
//tot[i]表示经过i个点的最长链的条数
bool vis[N];
void getrt(int x,int fa)
{
siz[x]=1;son[x]=0;
for(re int i=h[x],v;i;i=e[i].nxt)
if(!vis[v=e[i].v]&&v^fa)
{
getrt(v,x);
siz[x]+=siz[v];
son[x]=max(son[x],siz[v]);
}
son[x]=max(son[x],sum-siz[x]);
rt=son[x]<son[rt]?x:rt;
}//求重心模板
int st1[N],st2[N],top;
//st1存距离,st2存深度
void getdis(int x,int fa)
{
if(dep[x]>k) return;
st1[++top]=dis[x];
st2[top]=dep[x];
for(re int i=h[x],v;i;i=e[i].nxt)
if(!vis[v=e[i].v]&&v^fa)
{
dis[v]=dis[x]+e[i].w;
dep[v]=dep[x]+1;
getdis(v,x);
}
}
il int solve(int x)
{
re int pre=top=0,res=0;
memset(tot,0,sizeof(tot));
memset(len,0,sizeof(len));
tot[0]=1;//当前重心也有可能是一条最长链的起点！！！因为这里wa了好多次QAQ
for(re int i=h[x],v;i;i=e[i].nxt)
if(!vis[v=e[i].v])
{
dis[v]=dis[x]+e[i].w;
dep[v]=dep[x]+1;
pre=top;
getdis(v,x);
//处理出当前子树中的信息
for(re int j=pre+1;j<=top;++j)
{
if(len[k-st2[j]-1]+st1[j]>ans[0])
ans[0]=len[k-st2[j]-1]+st1[j],res=tot[k-st2[j]-1];
//当前子树上存在可以和之前子树上的链组成更优答案的链
else if(len[k-st2[j]-1]+st1[j]==ans[0]) res+=tot[k-st2[j]-1];
//当前子树上存在可以和之前子树上的链组成最优答案的链，那么累加方案数
}
for(re int j=pre+1;j<=top;++j)//给下一棵子树用
{
if(len[st2[j]]==st1[j]) ++tot[st2[j]];//累加方案
if(len[st2[j]]<st1[j]) tot[st2[j]]=1,len[st2[j]]=st1[j];//更新方案、长度
}
}
return res;
}
void getdiv(int x)
{
vis[x]=true;dis[x]=0;dep[x]=0;
re int pre=ans[0],tmp=solve(x);
if(ans[0]^pre) ans[1]=tmp;//更新方案
else ans[1]+=tmp;//累加方案
for(re int i=h[x],v;i;i=e[i].nxt)
if(!vis[v=e[i].v])
{
son[rt=0]=sum=siz[v];
getrt(v,0);
getrt(rt,0);
//其实这一次搜索可以不用，目的是将子树中的siz更新为以rt作为根的siz
getdiv(rt);
}
//点分治主体
}
}由于代码的核心部分上面都已经给出，这里就不给完整代码了。