【2020.11.30提高组模拟】删边(delete) 题解

T1 删边(delete)

题意

给一棵树删边,每次删的代价为这条边所连的两个点的子树中最大点权值。

求删光的最小代价。

n≤100000

做法

O(nlogn)

详见hash大犇的博客

O(n)

先选权值最大的点,那么它的贡献是 w[i]*degree[i]
,那么对于剩下几个连通块中权值最大的点,它们的贡献是 w[i]*(degree[i]+1),首先与他相连的边肯定有一端要选它,还有整个连通块和权值最大的点相连的边也有一端要选它(除了它和权值最大的点相连不用+1

但是这样太麻烦了,而且时间复杂度太大过不去,于是发现每个贡献都有已知的w[i],那么只用求degree[i],然后就可以尝试连一些新的边:从选权值最大的点开始,对于与它相连的每个连通块的边连到那个连通块的权值最大的点,这样建出的图degree[i]就是与点i相连的边的度数

这样时间复杂度还是过不去,再想亿想,求degree[i]又不一定要建出具体的图,建图不写出来,直接求degree[i]不就行了,本文完

以权值最大的点为根节点,对于每个父亲节点,如果他的某个儿子权值比它大,
那就把那个儿子的整颗子树移上去,把它作为自己的父亲节点,于是它的孙子成了它的兄弟,如果有很多个这样的儿子,那就把更大权值的儿子作为更小权值儿子的父亲

分析完了,怎么写呢?不用写

其实总的就是对于那种父亲节点,那样的儿子结点多了个儿子,而它自己少了个儿子,所以in[x]++,in[fa[x]]--就完事了

#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define int long long
#define re register
#define mod 998244353
#define inf 0x3f3f3f3f
using namespace std;
const int N=100005;
int n,ma,num,ans;
int w[N],s[N];
bool v[N];
vector<int> a[N];
template <class T> inline void read(T &x){
	x=0;int g=1; char s=getchar();
	for (;s>'9'||s<'0';s=getchar())	if (s=='-') g=-1;
	for (;s<='9'&&s>='0';s=getchar()) x=(x<<1)+(x<<3)+(s^48);
	x*=g;
}
queue <int> q;
void bfs()
{
	q.push(num);
	v[num]=1;
	while(q.size())
	{
		int x=q.front();q.pop();
		for (re int i=0;i<a[x].size();i++)
		if (!v[a[x][i]])
		{
			int y=a[x][i];
			v[y]=1;
			if (w[y]>w[x]) s[x]--,s[y]++;
			q.push(y);
		}	
	}
}
signed main()
{
	re int i,j,x,y,z;
	freopen("delete.in","r",stdin);freopen("delete.out","w",stdout);
	read(n);
	for (i=1;i<=n;i++) 
		{read(w[i]);if (w[i]>ma) ma=w[i],num=i;}
	for (i=1;i<n;i++)
	{
		read(x);read(y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for (i=1;i<=n;i++) s[i]=a[i].size();
	bfs();
	for (i=1;i<=n;i++) ans+=w[i]*s[i];
	printf("%lld",ans);
	
	return 0;
}          
上一篇:Food Webs


下一篇:neo4实现 Degree Centrality算法