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;
}