思路：将 $i$ 的子树的节点存到 $i$ 的后面（连续）。用查分实现 $p = 1$ 的修改为 $O(1)$。注意到 $p = 2$ 时可能不连续，我们暴力修改。重点！对于菊花图而言，我给出了如下优化：注意到当 $x$ 在树的倒数第二层时，其子节点一定连续，于是有 $O(1)$ 的修改。显然，这个是错解，如何hack掉这个代码？

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a;i <= b;i++)
const int Max = 1e6+5;
struct node{
	int to, next;
}g[2*Max];
int k, pre[Max];
void add(int u, int v)
{
	g[++k].to = v;
	g[k].next = pre[u];
	pre[u] = k;
}
int n, m, q, a[Max], b[Max], d[Max];
int sub[Max], f[Max], s[Max], dep[Max], mdep;//sub[i]以i为根的子树大小 f[i]为i号节点的父亲 
vector<int> son[Max];//son[i]即为i号节点的直接儿子 
void dfs(int u, int fa)
{
	sub[u] = 1;f[u] = fa;dep[u] = dep[fa]+1;mdep = max(mdep, dep[u]);
	for(int i = pre[u];i;i = g[i].next)
	{
		int v = g[i].to;
		if(v != fa)
		{
			dfs(v, u);
			sub[u] += sub[v];
			son[u].push_back(v);
			s[u]++;
		}
	}
}
int pos[Max], num = 0;//i号节点在新数组b中的位置 
void arrange(int cur)
{
	b[++num] = a[cur];pos[cur] = num;
	for(int i:son[cur])arrange(i);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n;
	rep(i, 1, n)cin >> a[i];
	rep(i, 1, n-1)
	{
		int u, v;
		cin >> u >> v;
		add(u, v);add(v, u);
	}
	dfs(1, 0);
	arrange(1);
	rep(i, 1, n)d[i] = b[i]-b[i-1];//差分
	cin >> m;
	while(m--)
	{
		int p, x, y;
		cin >> p >> x >> y;
		if(p == 1)
		{
			d[pos[x]] += y;
			d[pos[x]+sub[x]] -= y;
		}
		else
		{
			if(dep[x] == mdep-1)
			{
				d[pos[x]] += y;
				d[pos[x]+s[x]+1] -= y;
				if(x != 1)
	            {
	                d[pos[f[x]]] += y;
	    			d[pos[f[x]]+1] -= y;
	            }
				continue;
			}
			d[pos[x]] += y;
			d[pos[x]+1] -= y;
			for(int i:son[x])
			{
				d[pos[i]] += y;
				d[pos[i]+1] -= y;
			}	
			if(x != 1)
            {
                d[pos[f[x]]] += y;
    			d[pos[f[x]]+1] -= y;
            }
		}
	}
	rep(i, 1, n)b[i] = b[i-1]+d[i];
	cin >> q;
	while(q--)
	{
		int x;
		cin >> x;
		cout << b[pos[x]] << "\n";
	}
	return 0;
}

不加优化的100TLE

加了特判后的AC