【题解】CF68D：Half-decay tree

原题传送门
这道题目不难
发现总共$q$个询问，每次询问最多涉及到$h$个点，所以总共最多设计到$qh$个点
可以用$map$把以每个点为根的子树权值之和记录下来
修改操作直接把自己到根路径上所有点修改
查询操作不妨反向思考，从根节点开始往下断边，因为是二叉树所以每次只有两种断边可能，对应权值可以求出
由于期望的线性性直接加起来
终止条件是当前的最大值大于等于当前节点的map值
Code：

#include <bits/stdc++.h>
using namespace std;
int h, q;
map <int, int> mp;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

#define ls u << 1
#define rs u << 1 | 1

double dfs(int u, int Max){
	if (Max >= mp[u]) return Max;
	return 0.5 * (dfs(ls, max(Max, mp[u] - mp[ls])) + dfs(rs, max(Max, mp[u] - mp[rs])));
}

int main(){
	h = read(), q = read();
	while (q--){
		char c[10]; scanf("%s", c);
		if (c[0] == 'a'){
			int u = read(), w = read();
			while (u) mp[u] += w, u >>= 1;
		} else printf("%.8f\n", dfs(1, 0));
	}
	return 0;
}