自动搬运

查看原文

来自洛谷，原作者为

	ATZdhjeb 8 + 46 + 5

搬运于2025-08-24 23:04:49，当前版本为作者最后更新于2025-03-26 20:42:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

可爱猫猫题

令 $f_u$ 表示点 $u$ 的答案，即让以点 $u$ 为根的子树“超平衡”时，这个子树最少多重。那么有一个递推式是 $f_u=2\times\max\{f_l,f_r\}$，即先让其左右子树分别“超平衡”，再平衡自己。由此，有一个比较显然的结论是 $f_u = 2^{-d_u}\times\max 2^{d_x}a_x$，其中 $x$ 为 $u$ 子树内的一个叶子，$d_u$ 表示 $u$ 在树上的深度，$d_x$ 同理。证明可以考虑从下往上归纳，对于叶子显然成立，非叶子可以假设左右儿子成立，然后由上述递推式推得。

现在我们要求的问题即是单点修改、求子树 $\max$。但是由于这个东西比较大，不方便直接比较大小，所以实现时直接将答案存储为 $2^p\times q$ 的形式。对于比较形如 $2^{p_1}\times q_1$ 与 $2^{p_2}\times q_2$ 的数的大小的问题，可以发现当 $|p_1-p_2|\ge30$ 时可以直接判断，否则可以暴力计算比较。

然后就做完了，时间复杂度 $O(n\log n)$。

贴个核心代码，省略了一些缺省源，应该不影响阅读。

const int mod = 998244353;
using mint = Source::mint<mod>;

int n, q, a[400010], dfn[400010], siz[400010], dep[400010], cnt;
mint pw[400010];
vector<int> e[400010];

struct pint {
	int p, q;
	
	pint(int a = 0, int b = 0) {
		p = a;
		q = b;
	}
	
	bool operator < (pint b) const {
		int dp = p - b.p;
		if (dp > 29) return false;
		if (dp < -29) return true;
		if (dp < 0) {
			dp = -dp;
			return pw[dp].x * 1LL * b.q > q;
		}
		return pw[dp].x * 1LL * q < b.q;
	}
};

class segmentTree {
	private :
		pint tree[1600010];
		
		inline int getLeft(int u) { return u << 1; }
		
		inline int getRight(int u) { return u << 1 | 1; }
		
		inline void pushUp(int u) { tree[u] = max(tree[getLeft(u)], tree[getRight(u)]); }
		
	public :
		void update(int u, int l, int r, int x, pint k) {
			if (l == r) {
				tree[u] = k;
				return;
			}
			if (x <= (l + r) / 2) update(getLeft(u), l, (l + r) / 2, x, k);
			else update(getRight(u), (l + r) / 2 + 1, r, x, k);
			pushUp(u);
		}
		
		pint query(int u, int l, int r, int x, int y) {
			if (x <= l && r <= y) return tree[u];
			if (y <= (l + r) / 2) return query(getLeft(u), l, (l + r) / 2, x, y);
			if (x > (l + r) / 2) return query(getRight(u), (l + r) / 2 + 1, r, x, y);
			return max(query(getLeft(u), l, (l + r) / 2, x, y), query(getRight(u), (l + r) / 2 + 1, r, x, y));
		}
}tree;

void DFS(int u, int p) {
	siz[u] = 1;
	dfn[u] = ++ cnt;
	dep[u] = dep[p] + 1;
	for (int v : e[u]) if (v != p) DFS(v, u), siz[u] += siz[v];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> q;
	pw[0] = 1;
	rep (i,1,n + n + 1) pw[i] = pw[i - 1] * 2;
	rep (i,1,n) {
		char op1, op2;
		int u1, u2;
		cin >> op1 >> u1 >> op2 >> u2;
		if (op1 == 'W') u1 += n;
		if (op2 == 'W') u2 += n;
		e[i].emplace_back(u1);
		e[i].emplace_back(u2);
	}
	rep (i,n + 1,n + n + 1) cin >> a[i];
	DFS(1, 0);
	rep (i,1,n + 1) tree.update(1, 1, n + n + 1, dfn[i + n], pint(dep[i + n], a[i + n]));
	rep (i,1,q) {
		int op;
		cin >> op;
		if (op == 1) {
			int u, k;
			cin >> u >> k;
			u += n;
			a[u] = k;
			tree.update(1, 1, n + n + 1, dfn[u], pint(dep[u], a[u]));
		} else {
			int u;
			cin >> u;
			pint res = tree.query(1, 1, n + n + 1, dfn[u], dfn[u] + siz[u] - 1);
			mint ans = pw[res.p] * res.q;
			ans *= Source::quickPow<mod>(Source::quickPow<mod>(2, dep[u]), mod - 2);
			cout << ans.x << '\n';
		}
	}
	return 0;
}