E 题解_牛客博客

很经典的题目 .

首先 , 我们很容易判断所选的数都在某一个子树里的概率 , 为 $(\sum_{v \in subtree(u)} p_v)^k$ .

问题在于 , 如果所有点都在 $u$ 的子树里 , 那么它就在 $u$ 的父亲 , $u$ 的父亲的父亲的子树里面 .

这个问题的经典方案是差分 , 每个点的权值设为 $u - f a_{u}$ , 这样可以自动抵消 .

类似的题目 : [LNOI2014]LCA,[GXOI/GZOI2019]旧词 .

然后就需要用树链剖分 . 那么你的线段树需要维护区间的和 , 平方和 , 立方和 , ... , 五次方和 .

这也是经典问题 , 可以使用二项式定理维护复杂标记 . 类似的题目 : LG1471 方差 .

复杂度 $O(mk^2 \log^2 n)$ , 常数不要太大 , 注意取模运算尽量少一点 .

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10,MOD=1e9+7;
int n,m,k,p[MAXN],tmp[MAXN],tot;
vector<int> G[MAXN];
int qpow(int base,int p) {
	int res=1;
	while(p) {
		if(p&1) res=res*base%MOD;
		base=base*base%MOD,p>>=1;
	}
	return res;
}
int idx,fa[MAXN],top[MAXN],son[MAXN],sze[MAXN],dfn[MAXN],rev[MAXN];
void dfs1(int u,int f) {
	sze[u]=1,fa[u]=f,tmp[u]=p[u];
	for(auto v:G[u]) {
		if(v==f) continue;
		dfs1(v,u);
		sze[u]+=sze[v],tmp[u]=(tmp[u]+tmp[v])%MOD;
		if(sze[v]>sze[son[u]]) son[u]=v;	
	}
	return ;
}
void dfs2(int u) {
	dfn[u]=++idx,rev[idx]=u;
	if(son[u]) top[son[u]]=top[u],dfs2(son[u]);
	for(auto v:G[u]) if(!top[v]) top[v]=v,dfs2(v);	
}
//------------------------------------------------------------
struct POW {int v0,v1,v2,v3,v4,v5;};
int mmod(int v) {
	if(v>=MOD) v-=MOD;
	return v;	
}
POW operator +(POW a,POW b) {return {mmod(a.v0+b.v0),mmod(a.v1+b.v1),mmod(a.v2+b.v2),mmod(a.v3+b.v3),mmod(a.v4+b.v4),mmod(a.v5+b.v5)};}
POW operator *(POW a,int d) {
	if(!d) return a;
	int d1=d,d2=d*d%MOD,d3=d2*d%MOD,d4=d3*d%MOD,d5=d4*d%MOD;
	return {
		a.v0,
		(a.v0*d1%MOD+a.v1)%MOD,
		(a.v0*d2%MOD+2*a.v1%MOD*d1%MOD+a.v2)%MOD,
		(a.v0*d3%MOD+3*a.v1%MOD*d2%MOD+3*a.v2%MOD*d1%MOD+a.v3)%MOD,
		(a.v0*d4%MOD+4*a.v1%MOD*d3%MOD+6*a.v2%MOD*d2%MOD+4*a.v3%MOD*d1%MOD+a.v4)%MOD,
		(a.v0*d5%MOD+5*a.v1%MOD*d4%MOD+10*a.v2%MOD*d3%MOD+10*a.v3%MOD*d2%MOD+5*a.v4%MOD*d1%MOD+a.v5)%MOD
	};
}
int tag[MAXN<<2]; POW seg[MAXN<<2];
#define lson (k<<1)
#define rson (k<<1|1)
#define mid (l+r>>1)
void push_down(int k,int l,int r) {
	seg[lson]=seg[lson]*tag[k],seg[rson]=seg[rson]*tag[k];
	tag[lson]=mmod(tag[lson]+tag[k]),tag[rson]=mmod(tag[rson]+tag[k]),tag[k]=0;
	return ;
}
void update(int k,int l,int r,int x,int y,int v) {
	if(x<=l&&r<=y) return tag[k]=mmod(tag[k]+v),seg[k]=seg[k]*v,void();
	push_down(k,l,r);
	if(x<=mid) update(lson,l,mid,x,y,v);
	if(y>mid) update(rson,mid+1,r,x,y,v);
	return seg[k]=seg[lson]+seg[rson],void();
}
POW query(int k,int l,int r,int x,int y) {
	if(x<=l&&r<=y) return seg[k];
	push_down(k,l,r);
	if(y<=mid) return query(lson,l,mid,x,y);
	if(x>mid) return query(rson,mid+1,r,x,y);
	return query(lson,l,mid,x,y)+query(rson,mid+1,r,x,y);	
}
void build(int k,int l,int r) {
	if(l==r) return seg[k].v0=((rev[l]-fa[rev[l]])%MOD+MOD)%MOD,void();	
	build(lson,l,mid),build(rson,mid+1,r);
	seg[k]=seg[lson]+seg[rson];
}
//------------------------------------------------------------
void output(void) {
	int res;
	if(k==1) res=seg[1].v1;
	if(k==2) res=seg[1].v2;
	if(k==3) res=seg[1].v3;
	if(k==4) res=seg[1].v4;
	if(k==5) res=seg[1].v5;	
	res=res*qpow(qpow(tot,k),MOD-2)%MOD;
	res=(res+MOD)%MOD;
	cout<<res<<'\n';
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); 
	cin>>n>>m>>k;
	ffor(i,1,n) cin>>p[i],tot=mmod(tot+p[i]);
	ffor(i,1,n-1) {
		int u,v; cin>>u>>v;
		G[u].push_back(v),G[v].push_back(u);	
	}
	dfs1(1,0),top[1]=1,dfs2(1);
	build(1,1,n);
	ffor(i,1,n) update(1,1,n,i,i,tmp[rev[i]]);
	output();
	ffor(i,1,m) {
		int u,v; cin>>u>>v;
		int add=((v-p[u])%MOD+MOD)%MOD,pos=u;
		while(pos) update(1,1,n,dfn[top[pos]],dfn[pos],add),pos=fa[top[pos]];
		tot=((tot-p[u]+v)%MOD+MOD)%MOD,p[u]=v; output();
	}
	return 0;
}