自动搬运

查看原文

来自洛谷，原作者为

	watermonster 最菜SDUer

搬运于2025-08-24 21:44:11，当前版本为作者最后更新于2020-08-24 21:35:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很裸的一道点分治，感觉就是这道题的升级版。

显然我们就是要建出最短路径树，然后直接在树上跑点分治就行了。

首先，关于建树

题目要求我们按字典序最小的路径建树，但由于官方数据过水，貌似大部分题解都没管字典序(不过后来添加了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个点的简单路径长度为多长？长度为该最长长度的不同路径有多少条？

对于最长路径的长度，做法可以参考这里。我们可以开两个栈，一个存链长，一个存深度，若当前链经过节点数为$x$那么这条链就应该和之前子树中的一条经过$k-x-1$个节点的链组成答案（减1是因为当前的重心也是链上的点），如果比答案更长则更新长度和方案，如果一样长就直接累加方案。

点分治部分代码：

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);
			}
		//点分治主体
	}
}

由于代码的核心部分上面都已经给出，这里就不给完整代码了。