自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 22:43:53，当前版本为作者最后更新于2022-12-22 14:05:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

$\text{Link}$

题意

对于一个 $n$ 个结点的带边权的树 $T$，定义 $\text{dis}(x,y)$ 为 $T$ 中 $x\to y$ 路径上的边权和。再定义一个 $n$ 个结点的无向完全图 $p(T)=G$，其中 $\forall x,y\in [1,n]$，$G$ 中边 $(x,y)$ 的边权为 $\text{dis}(x,y)$。

定义 $f(T)$ 为 $p(T)$ 的最大生成树。特别的，若 $p(T)$ 的最大生成树不唯一，请立刻判断出并报告。

给定树 $T_0$ 和整数 $k$，求 $f^k(T_0)$。边权为正整数。

若 $\exists x\in[0,k-1]$ 使得 $p(f^x(T_0))$ 的最大生成树不唯一，输出 $-1$。否则，输出 $f^k(T_0)$ 的所有边权和对 $2^{32}$ 取模的结果。

$n\le 10^6$，$1\le k\le 10^7$。

思路

来补个严谨证明。

考虑 $k=1$ 的部分分。

使用 $\operatorname{Boruvka}$ 算法。我们对每个点找到距离它最远的点并与其连边。很显然，经过一次 $\operatorname{Boruvka}$ 算法，所有的点已经连通。原因是树上每个点距离最远的点为直径两端点之一，而直径两端点互相连接。

假设答案不是 $-1$，我们就已经得到了 $f(T_0)$ 了。来判断答案是不是 $-1$，共有以下情况：

• 直径不唯一

我们先证明，不会存在两条互不相交的直径。

反证，考虑存在下面的树，满足 $3\to 4$，$6\to 7$ 为两条直径。

不妨令 $x=x_1+x_2>0$，$a>b>0$，$c\ge d>0$。

显然，$a+b\ge a+x+c$，$c+d\ge a+x+c$，所以 $b\ge c+x$，$d\ge a+x$。所以 $b>c\ge d>a$，矛盾。当 $a=b$ 时也易证矛盾。

所以，树不存在两条互不相交的直径。我们还可以证明如果有多条直径，则对于每一条直径，必然有一条其他直径与它在一个端点相交。

于是我们可以找出一条直径 $x\to y$，算出所有的 $\operatorname{dis}(i,x)$ 和 $\operatorname{dis}(i,y)$，如果有 $\operatorname{dis}(i,x)=\operatorname{dis}(x,y)$ 或 $\operatorname{dis}(i,y)=\text{dis}(x,y)$（$i\ne x,i\ne y$）则直径不唯一。

直径不唯一时答案也不一定为 $-1$。当所有直径有同一个端点（具体为上述两种情况仅满足一个），设为 $x$，并且所有点到 $x$ 距离都大于到另一个端点的距离，并且 $k=1$ 的时候，答案不为 $-1$，其余情况都为 $-1$。

考虑找出一条直径，枚举转折点 $i$，找出 $i$ 子树内 $dis(i,k)$ 最大的两个 $k$，则直径为 $\max(\text{dis}(i,k_1)+\text{dis}(i,k_2))$，树形 $\text{dp}$ 即可。

• 直径唯一

则此类情况下，答案为 $-1$ 当且仅当有一个点 $i$ 到直径两端距离相等。

接下来考虑 $k>1$ 的情况。

依然考虑以上算法，考虑一次操作后树为两个点分别挂着一堆点（分别将两个点集记为 $S_x,S_y$）。令 $S_x$ 中与 $x$ 相连边最长的点为 $m_x$，$m_y$ 同理。考虑由于 $x\to y$ 的边权为此时树中的最大边权，此时树的直径为 $m_x\to m_y$，则 $S_x$ 中的点经历这次操作都会连到 $m_y$，且边权为原来的加上 $v_{x\to y}+v_{y\to m_y}$，$S_y$ 中的点同理。新树中 $v_{m_x\to m_y}$ 等于旧树中 $v_{x\to y}+v_{x\to m_x}+v_{y\to m_y}$。

考虑边权的增长是指数级的，我们不能直接维护，必须在模 $2^{32}$ 意义下维护相对顺序。考虑拿两个队列 $q_1,q_2$ 维护 $S_x,S_y$ 中 $v_{x\to p}$ 的相对顺序。考虑一次操作后先得出 $q_1,q_2$ 并进行排序。考虑一次操作，我们会取出两边的最大值并将其置为零，将其余的整体加上一个正数，并将 $x$ 加入队列。考虑维护整体加的 $tag$，由于 $x$ 原先是最小值 $0$，我们将 $-tag$ 加入最后即可。

再考虑判 $-1$：

• 直径不唯一

即 $S_x$ 或 $S_y$ 中前两大值相等。不能直接判断，因为我们的边权是在模 $2^{32}$ 下考虑的。但是我们考虑一次操作后只会取 $k-1$ 次，我们只需要在一次操作后的 $S_x$ 和 $S_y$ 中判断 $i\in[1,\min(n,k-1)]$ 中是否 $q_{o,i}=q_{o,i+1}$ 即可，需要注意，当 $S_x$ 与 $S_y$ 有一个空的时候不应判断这种情况，因为此时直径不唯一但有同一端点。

或者你加个哈希也可以。

这个情况是答案必然为 $-1$ 的。

• 直径唯一

不可能有任何一个点到新直径两端距离相等，因为旧直径是旧的树中边权最大的。

综上，我们做到了 $O(n\log n+k)$ 的复杂度。瓶颈是排序。

代码细节比较多，就贴上来了：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ui unsigned 
namespace IO{//by cyffff
	
}
const int N=1e6+10;
int n,k,head[N],cnt;
struct Edge{
	int to,nxt,w;
}a[N<<1];
inline void add(int u,int v,int w){
	cnt++;
	a[cnt].to=v;
	a[cnt].nxt=head[u];
	a[cnt].w=w;
	head[u]=cnt;
}
int s,t;
ll mx,dep[N][2],dis;
inline void dfs(int x,int fa,int tp){
	if(!fa) dep[x][tp]=0;
	for(int i=head[x];i;i=a[i].nxt){
		int t=a[i].to;
		if(t==fa) continue;
		dep[t][tp]=dep[x][tp]+a[i].w;
		dfs(t,x,tp);
	}
}
vector<ll>s1,s2;
queue<ui>d1,d2;
ui tag1,tag2,di,ans;
/*
7 1
1 1
2 2
1 4
2 4
4 4
5 4
*/
int main(){
//	freopen("16.in","r",stdin);
	n=read(),k=read();
	for(int i=2;i<=n;i++){
		int f=i-read(),w=read();
		add(f,i,w),add(i,f,w);
	}
	dfs(1,0,0);
	for(int i=1;i<=n;i++)
		if(dep[i][0]>mx) mx=dep[i][0],s=i;
	dfs(s,0,0);
	for(int i=1;i<=n;i++)
		if(dep[i][0]>dis) dis=dep[i][0],t=i;
	dfs(t,0,1);
	bool fl1=0,fl2=0;
	for(int i=1;i<=n;i++){
		if(i==s||i==t) continue;
		if(dep[i][0]==dep[t][0]) fl1=1;
		if(dep[i][1]==dep[s][1]) fl2=1;
	}
	if(fl1&&fl2) return puts("-1"),0;
	if((fl1||fl2)&&k>1) return puts("-1"),0;
	if(fl1){
		for(int i=1;i<=n;i++){
			if(i==s||i==t) continue;
			if(dep[i][0]<dep[i][1]) return puts("-1"),0;
		}
	}
	if(fl2){
		for(int i=1;i<=n;i++){
			if(i==s||i==t) continue;
			if(dep[i][0]>dep[i][1]) return puts("-1"),0;
		}
	}
	for(int i=1;i<=n;i++){
		if(i==s||i==t) continue;
		if(dep[i][0]==dep[i][1]) return puts("-1"),0;
		if(dep[i][0]>dep[i][1]) s1.push_back(dep[i][0]);
		else s2.push_back(dep[i][1]);
	}
	sort(s1.begin(),s1.end(),greater<ll>());
	sort(s2.begin(),s2.end(),greater<ll>());
	if(s1.size()&&s2.size()){
    	for(int i=0;i+1<s1.size()&&i<min(n,k-1);i++)
    		if(s1[i]==s1[i+1]) return puts("-1"),0;
    	for(int i=0;i+1<s2.size()&&i<min(n,k-1);i++)
    		if(s2[i]==s2[i+1]) return puts("-1"),0;
	}
	for(auto x:s1) d1.push((ui)x);//,printf("%d ",x);puts("");
	for(auto x:s2) d2.push((ui)x);//,printf("%d ",x);puts("");
	di=dis;
	for(int i=2;i<=k;i++){
		ui x=0,y=0;
		bool fl1=0,fl2=0;
		if(!d1.empty()) x=d1.front()+tag1,d1.pop(),fl1=1;
		if(!d2.empty()) y=d2.front()+tag2,d2.pop(),fl2=1;
		if(fl1) d1.push(-tag1),tag1+=y+di;
		if(fl2) d2.push(-tag2),tag2+=x+di;
		di+=x+y;
//		printf("%d %d %d %d %d\n",x,y,tag1,tag2,di);
	}
	while(!d1.empty()) ans+=d1.front()+tag1,d1.pop();
	while(!d2.empty()) ans+=d2.front()+tag2,d2.pop();
	ans+=di;
	write(ans);
	flush();
}