自动搬运

查看原文

来自洛谷，原作者为

	winxp_qwq 退役菜鸡

搬运于2025-08-24 21:54:08，当前版本为作者最后更新于2018-02-25 19:28:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

先膜楼下dalao为敬，然而由于本蒟蒻太菜了，只会树剖的nlog^2n卡常做法

30分做法：

暴力续aaa，乖乖♂站好即可

50分做法：

考虑每个aaa对答案的贡献，每个点以还未续掉的点数为权值，

注意到每个点续掉每个aaa时权值都会-1 (-1s), 因此先续码力大的aaa总是对的，排完序每次跳到根，路径系数-1即可。

而且本题要求最大值，却还要在mod的意义下计算，这样贪心求解之后才可以放心膜。

70~100分做法

注意到续aaa的过程每次需要走树上到根的路径，需要搞两个操作：

1.求到根路径的权值和

2.将到根路径权值-1

自然想到树剖

于是打了一发，发现最后一个点TLE了，显然nlog^2n不是正解，但是与时限相差也不大。

于是开始卡常。。。。。。 我们用树状数组代替线段树对链剖进行维护，因为树状数组对上面的操作完全可以胜任，而且常数小！

这样就能AC此题，得到全部的100分。

最后按例代码：

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define maxn 500666
#define mod 1000000007LL
#define mid ((l+r)>>1)
LL n,hhh=0;
struct aaa{
	LL va;
	LL po;
};
bool operator < (aaa a1,aaa a2){
	return a1.va<a2.va;
}
priority_queue <aaa> pq;
LL fa[maxn]={0},w[maxn]={0};
vector <LL> ed[maxn];
LL hs[maxn]={0},tp[maxn]={0},dfn[maxn]={0},tt=1;
LL cf[maxn]={0};
void dfs1(LL a){
	if(a==0) return;
	w[a]=1;hs[a]=0;
	for(LL b=0;b<ed[a].size();b++)
	if(fa[a]!=ed[a][b])
	{
		fa[ed[a][b]]=a;
		dfs1(ed[a][b]);
		w[a]+=w[ed[a][b]];
		if(w[ed[a][b]]>w[hs[a]]) hs[a]=ed[a][b];
	}
}
void dfs2(LL a){
	if(a==0) return;
	tp[a]= a==hs[fa[a]]? tp[fa[a]]:a;
	dfn[a]=tt++;
	dfs2(hs[a]);
	for(LL b=0;b<ed[a].size();b++)
	if(ed[a][b]!=fa[a]&&ed[a][b]!=hs[a]) dfs2(ed[a][b]);
}
//BIT
LL lowbit(LL x) {return (-x)&x;} 
LL bit[3][maxn]={0};
void add(LL a,LL x,LL c){
	while(x<=n)
	{
		bit[a][x]+=c;
		x+=lowbit(x);
	}
}
LL qu(LL a,LL x){
	LL ret=0;
	while(x)
	{
		ret+=bit[a][x];
		ret%=mod;
		x-=lowbit(x);
	}
	return ret;
}
LL qz(LL x){
	return ((qu(1,x)*(x+1)-qu(2,x))%mod+mod)%mod;
}
//.......
void xu(LL a,LL v){
	LL b,c,d;
	while(a)
	{
		c=tp[a];
		hhh+=(qz(dfn[a])-qz(dfn[c]-1))*v;
		hhh%=mod;
		add(1,dfn[c],-1);
		add(1,dfn[a]+1,1);
		add(2,dfn[c],-dfn[c]);
		add(2,dfn[a]+1,dfn[a]+1);
		a=fa[c];
	}
}
int main(){
	scanf("%lld",&n);
	LL a,b,c,i,j,k;
	aaa tmp;
	for(a=1;a<n;a++)
	{
		scanf("%lld%lld",&i,&j);
		ed[i].push_back(j);
		ed[j].push_back(i);
	}
	for(a=1;a<=n;a++)
	{
		scanf("%lld",&b);
		tmp.va=b;tmp.po=a;
		pq.push(tmp);
	}
	dfs1(1);dfs2(1);
	for(a=1;a<=n;a++) cf[dfn[a]]=w[a];
	for(a=n;a>=1;a--) cf[a]-=cf[a-1];
	for(a=1;a<=n;a++) add(1,a,cf[a]);
	for(a=1;a<=n;a++) add(2,a,cf[a]*a);
	while(pq.size())
	{
		tmp=pq.top();pq.pop();
		xu(tmp.po,tmp.va);
	}
	printf("%lld\n",hhh);
	return 0;
}