自动搬运

查看原文

来自洛谷，原作者为

	素质玩家孙1超 天道酬勤！

搬运于2025-08-24 22:12:43，当前版本为作者最后更新于2019-11-09 23:45:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题目是那天打比赛时想骗更多的分但想不到正解

眼看着就要吃晚饭了，马上飞去小店买面包吃回来时想出的乱搞做法

大致题意

给你一棵树，每条边有一个重要度：若一条道路无法使用，会导致有 t对路口无法相互抵达，则t就是该道路的重要度。

施工会使以某一个点的周围与之距离不超过k的点被删，从而与之连的边被删，求被删的边的重要度和的最大值

正解是树上容斥然而我这么菜怎么会想到正解

而我介绍的方法是玄学乱搞

思路：

对于处理边权（重要度），我们dfs搜一遍，边权就是以该边左端点为根的子树大小乘上剩下端点数

具体处理方法(size[i]表示以i为根的子树大小,in[k]表示第k条边的重要度)

inline void dfs(int x,int father)
{
	size[x]=1;
	for(int k=First[x];k;k=Next[k])
	{
		if(to[k]==father) continue;
		dfs(to[k],x);
		size[x]+=size[to[k]];
		in[k]=size[to[k]]*(n-size[to[k]]);
	}
}

那么处理好了边权，我们这么找出施工中的那个点呢？

相信大家都能想到朴素算法，对于每一个点搜索并记录，

但是如果是链的话，时间复杂度k * n，而菊花图则会被卡到n * n，

显然容易超时,这时我们怎么办呢？

下面开始胡说讲解重点

(注:这种想法十分不严谨，但不失为骗分好方法)

我们需要考虑选择什么样的点作为起点更有可能使得结果最大

这时候想到重要度的定义，如果一条边重要度大的话，那么被这条边分开的两个连通块的点数的乘积就会多

我们可以不严谨地认为，在重要度大的边附近的边重要度大的概率大

相反，在比较边界的地方，重要度小的边附近的边重要的小的概率大

那么，我们就考虑记录每个点连接的边的重要度之和，并按此排序

先从我们认为最优的开始搜索

在搜索得快时间超限的时候把他打断，输出此时的答案即可满分

（我自己比赛时在dfs最里层加了一个计数的变量,当他大于10000000时打断最后还跑得挺快）

上代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn=3e4+5;
#define int long long 
int ans,number;
inline int R()
{
	char c;int sign=1,res=0;
	while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1;
	res+=c-'0';
	while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
	return res*sign;
}//读入优化 
int First[Maxn],Next[Maxn*2],to[Maxn*2],cnt,n,K;
int in[Maxn*2],size[Maxn];
struct Point
{
	int we,id;
}a[Maxn];//记录每个点连结的边的重要度和其编号 
bool cmp(Point x,Point y)
{
	return x.we>y.we;
}
inline void add(int z,int y)
{
	Next[++cnt]=First[z];
	First[z]=cnt;
	to[cnt]=y;//加边 
}
inline void dfs(int x,int father)//第一边预处理的dfs 
{
	size[x]=1;
	for(int k=First[x];k;k=Next[k])
	{
		if(to[k]==father) continue;
		dfs(to[k],x);
		size[x]+=size[to[k]];//记录子树大小 
		in[k]=size[to[k]]*(n-size[to[k]]);//计算边的重要度 
		a[x].we+=in[k];//统计点的权值（连出去的边的重要度和） 
		a[to[k]].we+=in[k];
	}
}
int now;
inline void dfs2(int x,int father,int num)
{//x为该节点，father为其父亲,num为其到最初点的距离 
	if(num>K) return;
	number++;//计数 
	for(int k=First[x];k;k=Next[k])
	{
		if(to[k]==father) continue;
		now+=in[k];//统计重要度 
		dfs2(to[k],x,num+1);
	}
	return;
}
signed main()
{
	n=R();K=R();int x,y;
	for(int i=1;i<=n;i++) a[i].id=i;
	for(int i=1;i<n;i++)
	{
		x=R();y=R();
		add(x,y);add(y,x);
	}//加边 
	dfs(1,0);//预处理 
	for(int i=1;i<=cnt;i+=2) 
	in[i]=in[i+1]=max(in[i],in[i+1]);
	//第2i-1条与第2i为同一条边，只是方向不同 
	sort(a+1,a+1+n,cmp);//按权值排序 
	for(int i=1;i<=n;i++)
	{
		now=0;
		if(number>10000000) break;//及时退出，防止tle 
		dfs2(a[i].id,0,0);//记录答案 
		if(now>ans) ans=now;//更新答案 
	}
	printf("%lld\n",ans);
}

觉得好别忘点个赞再走qwq