11.12 T2

没时间了，随便口胡一下吧。没听评讲。

我们对每一个点计算贡献，答案就是所有点贡献的和。比如 x 的贡献就是分母为

i = root \to x_{fa}|sum(i)

乘起来，分子为

i = nxt(root) \to x | w(i)

乘起来，再对着这个分数乘 a_i。

我们先改 w_u，再改 a_u。

对于 w(u) 的修改，会直接修改 sum_{fa_u}，还会修改 w(u)。我们看这会对哪些点的贡献产生影响，发现会影响 fa 子树，不包括 fa，的分母。会影响 u 子树，包括 u，的分子。如果我们把这棵树变成 dfs 序，就是区间乘。

然后对于 a_u 的修改，相当于对于点 u 的值先区间除再区间乘，或者是对于差值区间加，不过这应该不太重要吧。

于是得到了一个需要维护区间乘法，区间加法，区间求和，或者只是区间乘法，区间求和的线段树。

参考线段树 2 吧。

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 1e5+10, mod = 998244353;

int mi(int x,int k) {
	return k?1ll*mi(1ll*x*x%mod,k/2)*(k%2?x:1)%mod:1;
}

int inv(int x) {
	return mi(x,mod-2);
}
int n;
vector<int>e[N]; int fa[N];
int w[N],a[N],sum[N],val[N];

int L[N],R[N],d[N],dn;
void dfs_val(int u) {
	L[u] = ++dn;
	d[dn] = u;
	for (int v : e[u]) {
		// cout << u << ' '<< v << ' ' << val[u] << ' ' << w[v] << ' ' << sum[u] << endl;
		val[v] = 1ll*val[u] * w[v] % mod * inv(sum[u]) % mod;
		dfs_val(v);
	}
	R[u] = dn;
}

#define mid ((l+r)>>1)
#define ls (u*2)
#define rs (u*2+1)
struct Node{
	int val,tag;
}c[N<<2];


void pushup(int u) {
	c[u].val = (c[ls].val + c[rs].val) % mod;
}
void build(int u,int l,int r) {
	c[u].tag=1;
	if (l == r) {
		c[u].val = val[d[l]] * a[d[l]] % mod;
		return ;
	}
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(u);
}
void addtag(int u,int x) {
	(c[u].val *= x) %= mod;
	(c[u].tag *= x) %= mod;
}

void pushdw(int u) {
	if (c[u].tag != 1) {
		addtag(ls,c[u].tag), addtag(rs,c[u].tag);
		c[u].tag = 1;
	}
}
void upd(int u,int l,int r,int L,int R,int x) {
	if (L <= l && r<= R) {
		addtag(u,x);
		return ;
	}
	pushdw(u);
	if (L <= mid) upd(ls,l,mid,L,R,x);
	if (R > mid) upd(rs,mid+1,r,L,R,x);
	pushup(u);
}
signed main() {
	//freopen("b.in","r",stdin);
	//freopen("b.out","w",stdout);
	cin.tie(nullptr) -> sync_with_stdio(false);
	cin>>n;
	// cout << "DOWN";
	for (int i=2;i<=n;i++) {
		int x;
		cin>>x;
		fa[i] = x;
		e[x].push_back(i);
	}

	for (int i=1;i<=n;i++) {cin>>w[i];}
	for (int i=1;i<=n;i++) {cin>>a[i];}
	for (int i=1;i<=n;i++) {
		for (int v : e[i]) {
			sum[i] += w[v];
			sum[i] %= mod;
		}
	}
	val[1] = 1;dfs_val(1);
	build(1,1,n);

	cout << c[1].val % mod<< endl;
	int Q; cin>>Q;
	while(Q--) {
		int u,neww,newa;
		cin>>u>>neww>>newa;
		int fu = fa[u],newsum = sum[fu] - w[u] + neww;
		int invw = inv(w[u]), invsum = inv(newsum), inva = inv(a[u]);
		// cout << L[fu] << ' ' << R[fu] << endl;
		if (u != 1) {
			upd(1,1,n,L[fu]+1,R[fu],sum[fu]);
			upd(1,1,n,L[fu]+1,R[fu],invsum);
			upd(1,1,n,L[u],R[u],invw);
			upd(1,1,n,L[u],R[u],neww);
		}
		upd(1,1,n,L[u],L[u],inva);
		upd(1,1,n,L[u],L[u],newa);

		cout << c[1].val % mod << '\n';

		sum[fu] = newsum;
		w[u] = neww;
		a[u] = newa;
	}
	return 0;
}

文章操作

相关推荐

评论

11.12 T2