JZOJ6359. 【NOIP2019模拟2019.9.15】小ω的树

Description

点数n<=3e5,询问m<=3e4

Solution

• 显然有一种暴力的想法，按照边权从大到小排序，然后连边，答案就是最大的：当前连通块的点权和sum*当前的边权val。
• 根据连边（并查集）的顺序，我们可以构造出一颗克鲁斯卡尔重构树

克鲁斯卡尔重构树：
link(x,y)：新建z，fa[x]=z,fa[y]=z;

• 考虑如果将a[u]变成v，那么对于包括这个点的连通块的贡献就会改变(a[u]-v)*边权
• 这些连通块所代表的节点实际上就是重构树中的一条到根的链。
• 如果我们只有一条链，每一次将一个前缀的节点修改，每一次查询所有节点的最大值。
• 这个问题可以用分块解决。
• 对于每一个块都用一个凸壳维护一下，在修改时记录一个tag，二分求最大值。
• 散块直接暴力重构。
• 把序列放到链上，我们直接用树链剖分，每一条重链都分别分块，链的长度最大每次少一半，所以时间$O(Nsqrt nlog_n)$
• 查询的时候将所有的块的答案记到一个堆中（set），每一次修改块的时候修改一下，就可以了。

#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#define maxn 600005
#define ll long long 
#define db double
using namespace std;

int n,m,i,j,k,a[maxn],x,y,u,v;
int tot,fa[maxn];
ll val[maxn],sum[maxn],Kb[maxn],Mx[maxn],del[maxn];
struct edge{int x,y,z;} e[maxn];
int cmp(edge a,edge b){return a.z>b.z;}
int E[maxn][2],vis[maxn],Fa[maxn],sz[maxn],gs[maxn];
int cnt,d[maxn],tmp[maxn];
int totb,fr[maxn];
int Len,st[maxn],en[maxn],tot0[maxn],D[maxn];
int cmp2(int a,int b){return val[a]<val[b]||val[a]==val[b]&&Kb[a]>Kb[b];}

multiset<ll> s;
multiset<ll>::iterator it;

void read(int &x){
	x=0; char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
}

int father(int x){return (fa[x]==x)?x:fa[x]=father(fa[x]);}

void link(int i){
	int x=father(e[i].x),y=father(e[i].y);
	tot++,fa[x]=tot,fa[y]=tot,fa[tot]=tot;
	E[tot][0]=x,E[tot][1]=y,sz[tot]=sz[x]+sz[y],Fa[x]=Fa[y]=tot;
	if (sz[x]>sz[y]) gs[tot]=x; else gs[tot]=y;
	val[tot]=e[i].z;
	sum[tot]=sum[x]+sum[y];
	Kb[tot]=val[tot]*sum[tot];
}

db Jiao(int i,int j){
	return 1.0*(Kb[j]-Kb[i])/(val[i]-val[j]);
}

void Predo(int t){
	tmp[0]=0;
	for(int i=st[t];i<=en[t];i++) tmp[++tmp[0]]=d[i];
	sort(tmp+1,tmp+1+tmp[0],cmp2);
	tot0[t]=1,D[st[t]]=tmp[1];
	for(int i=2;i<=tmp[0];i++) if (val[tmp[i]]!=val[tmp[i-1]]){
		while (tot0[t]>1&&Jiao(tmp[i],D[st[t]+tot0[t]-1])<Jiao(tmp[i],D[st[t]+tot0[t]-2]))
			tot0[t]--;
		tot0[t]++;
		D[st[t]+tot0[t]-1]=tmp[i];
	}
	Mx[t]=0;
	for(int i=1;i<=tmp[0];i++) 
		Mx[t]=max(Mx[t],Kb[tmp[i]]);
	if (Mx[t]) s.insert(Mx[t]);
}

void upd(int t){
	Mx[t]=val[D[st[t]]]*del[t]+Kb[D[st[t]]];
	int l=st[t]+1,r=st[t]+tot0[t]-1;
	while (l<=r){
		int mid=(l+r)/2;
		Mx[t]=max(Mx[t],val[D[mid]]*del[t]+Kb[D[mid]]);
		if (Jiao(D[mid-1],D[mid])<=del[t]) l=mid+1; else r=mid-1;
	}
	if (Mx[t]) s.insert(Mx[t]);
}

void San(int u,int delta){
	int k=fr[u];
	if (Mx[k]) {
		it=s.find(Mx[k]);
		s.erase(it);
	}
	for(int i=st[k];i<=en[k];i++){
		Kb[d[i]]+=val[d[i]]*delta;
		if (d[i]==u) break;
	}
	for(int i=st[k];i<=en[k];i++) 
		Kb[d[i]]+=val[d[i]]*del[k];
	del[k]=0;
	Predo(k);	
}

int main(){
	freopen("tree13.in","r",stdin);
	freopen("ceshi.out","w",stdout);
//	freopen("tree.in","r",stdin);
//	freopen("tree.out","w",stdout);
	read(n),read(m);
	for(i=1;i<=n;i++) read(a[i]);
	for(i=1;i<n;i++) read(e[i].x),read(e[i].y),read(e[i].z);
	sort(e+1,e+n,cmp);
	for(i=1;i<=n;i++) fa[i]=i,val[i]=0,sum[i]=a[i],sz[i]=1;
	tot=n; for(i=1;i<n;i++) link(i);
	for(i=tot;i>=1;i--) if (!vis[i]){
		int cnt0=0;
		for(x=i;x;x=gs[x]) vis[x]=1,++cnt0,d[cnt+cnt0]=x;
		int K=sqrt(cnt0);
		for(j=cnt+1;j<=cnt+cnt0;j+=K) {
			totb++;
			st[totb]=Len+1,en[totb]=Len+min(cnt+cnt0-j+1,K);
			tmp[0]=0;
			for(k=st[totb];k<=en[totb];k++) 
				fr[d[k]]=totb;
			Predo(totb);
			Len+=min(cnt+cnt0-j+1,K);
		}
		cnt+=cnt0;
	}
	while (m--){
		read(u),read(v);
		San(u,v-a[u]);
		x=Fa[d[st[fr[u]]]];
		while (x){
			k=fr[x];
			if (x==d[en[k]]){
				if (Mx[k]) {
					it=s.find(Mx[k]);
					s.erase(it);
				}
				del[k]+=v-a[u];
				upd(k);
			} else San(x,v-a[u]);
			x=Fa[d[st[k]]];
		}
		a[u]=v;
		it=s.end(); it--;
		printf("%lld
",*it);
	}
}