没想到一个点到 1 的贡献和到 u 的贡献存在比例关系, 只要乘以 deg[ u ] * m[ u ], m[ u ] 表示 u 到 1, 所成的系数。
然后我们用dfs序建出线段树后, 维护每个点乘的系数, 区间值的和就可以了。
#include#define LL long long#define LD long double#define ull unsigned long long#define fi first#define se second#define mk make_pair#define PLL pair #define PLI pair #define PII pair #define SZ(x) ((int)x.size())#define ALL(x) (x).begin(), (x).end()#define fio ios::sync_with_stdio(false); cin.tie(0);using namespace std;const int N = 2e5 + 7;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const int mod = 1e9 + 7;const double eps = 1e-8;const double PI = acos(-1);template inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;}template inline void sub(T& a, S b) {a -= b; if(a < 0) a += mod;}template inline bool chkmax(T& a, S b) { return a < b ? a = b, true : false;}template inline bool chkmin(T& a, S b) { return a > b ? a = b, true : false;}int n, v1, q, qus[N][4];int in[N], ot[N], idx;int v[N], deg[N];vector G[N];#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1struct segmentTree { int sum[N << 2], mul[N << 2], k[N << 2]; inline void pull(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; if(sum[rt] >= mod) sum[rt] -= mod; } inline void push(int rt) { if(mul[rt] != 1) { sum[rt << 1] = 1LL * sum[rt << 1] * mul[rt] % mod; sum[rt << 1 | 1] = 1LL * sum[rt << 1 | 1] * mul[rt] % mod; k[rt << 1] = 1LL * k[rt << 1] * mul[rt] % mod; k[rt << 1 | 1] = 1LL * k[rt << 1 | 1] * mul[rt] % mod; mul[rt << 1] = 1LL * mul[rt << 1] * mul[rt] % mod; mul[rt << 1 | 1] = 1LL * mul[rt << 1 | 1] * mul[rt] % mod; mul[rt] = 1; } } void build(int l, int r, int rt) { mul[rt] = 1; if(l == r) { if(l == 1) sum[rt] = v1, k[rt] = 1; else sum[rt] = 0, k[rt] = 0; return; } int mid = l + r >> 1; build(lson); build(rson); pull(rt); } void updateS(int L, int R, int val, int l, int r, int rt) { if(R < l || r < L || R < L) return; if(L <= l && r <= R) { sum[rt] = 1LL * sum[rt] * val % mod; k[rt] = 1LL * k[rt] * val % mod; mul[rt] = 1LL * mul[rt] * val % mod; return; } push(rt); int mid = l + r >> 1; updateS(L, R, val, lson); updateS(L, R, val, rson); pull(rt); } void updateP(int p, int val, int l, int r, int rt) { if(l == r) { sum[rt] = 1LL * val * v[p] % mod; k[rt] = val; mul[rt] = 1; return; } push(rt); int mid = l + r >> 1; if(p <= mid) updateP(p, val, lson); else updateP(p, val, rson); pull(rt); } int querySum(int L, int R, int l, int r, int rt) { if(R < l || r < L || R < L) return 0; if(L <= l && r <= R) return sum[rt]; push(rt); int mid = l + r >> 1; return (querySum(L, R, lson) + querySum(L, R, rson)) % mod; } int queryK(int p, int l, int r, int rt) { if(l == r) return k[rt]; push(rt); int mid = l + r >> 1; if(p <= mid) return queryK(p, lson); else return queryK(p, rson); }} Tree;void dfs(int u) { in[u] = ++idx; for(auto& v : G[u]) dfs(v); ot[u] = idx;}int power(int a, int b) { int ans = 1; while(b) { if(b & 1) ans = 1LL * ans * a % mod; a = 1LL * a * a % mod; b >>= 1; } return ans;}int main() { n = 1; scanf("%d%d", &v1, &q); v[1] = v1; for(int i = 1; i <= q; i++) { scanf("%d", &qus[i][0]); if(qus[i][0] == 1) { scanf("%d%d", &qus[i][1], &qus[i][3]); qus[i][2] = ++n; G[qus[i][1]].push_back(qus[i][2]); } else { scanf("%d", &qus[i][1]); } } dfs(1); for(int i = 1; i <= n; i++) deg[i] = 1; Tree.build(1, n, 1); for(int i = 1; i <= q; i++) { if(qus[i][0] == 1) { int fa = qus[i][1], u = qus[i][2]; v[in[u]] = qus[i][3]; Tree.updateS(in[fa], ot[fa], 1LL * (deg[fa] + 1) * power(deg[fa], mod - 2) % mod, 1, n, 1); deg[fa]++; Tree.updateP(in[u], Tree.queryK(in[fa], 1, n, 1), 1, n, 1); } else { int u = qus[i][1]; int ans = Tree.querySum(in[u], ot[u], 1, n, 1); ans = 1LL * ans * deg[u] % mod; ans = 1LL * ans * power(Tree.queryK(in[u], 1, n, 1), mod - 2) % mod; printf("%d\n", ans); } } return 0;}/**/