51nod1462树据结构（树链剖分+线段树）

#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int maxn&＃61;200010, inf&＃61;1e9;
struct poi{int too, pre;}e[maxn<<1];
struct tjm{ll deltat, deltav, deltatv;}tree[maxn<<2];
int n, m, tott, tot, ty, x, y, z;
int fa[maxn], d[maxn], size[maxn], top[maxn], w[maxn], last[maxn], son[maxn];
char buf[8000000], *ptr&＃61;buf-1;
inline void read(int &k)
{int f&＃61;1; k&＃61;0; char c&＃61;*&＃43;&＃43;ptr;while(c<&＃39;0&＃39; || c>&＃39;9&＃39;) c&＃61;&＃61;&＃39;-&＃39;&&(f&＃61;-1), c&＃61;*&＃43;&＃43;ptr;while(c<&＃61;&＃39;9&＃39; && c>&＃61;&＃39;0&＃39;) k&＃61;k*10&＃43;c-&＃39;0&＃39;, c&＃61;*&＃43;&＃43;ptr;k*&＃61;f;
}
inline void add(int x, int y){e[&＃43;&＃43;tot]&＃61;(poi){y, last[x]}; last[x]&＃61;tot;}
void dfs1(int x)
{size[x]&＃61;1;for(int i&＃61;last[x], too;i;i&＃61;e[i].pre){d[too&＃61;e[i].too]&＃61;d[x]&＃43;1;dfs1(too);size[x]&＃43;&＃61;size[too];if(size[too]>size[son[x]]) son[x]&＃61;too;}
}
void dfs2(int x, int tp)
{top[x]&＃61;tp; w[x]&＃61;&＃43;&＃43;tott; if(son[x]) dfs2(son[x], tp);for(int i&＃61;last[x], too;i;i&＃61;e[i].pre)if((too&＃61;e[i].too)!&＃61;son[x]) dfs2(too, too);
}
inline void addone(int x, ll deltat, ll deltav, ll deltatv)
{tree[x].deltatv&＃43;&＃61;deltatv&＃43;deltav*tree[x].deltat;tree[x].deltat&＃43;&＃61;deltat;tree[x].deltav&＃43;&＃61;deltav;
}
inline void down(int x)
{addone(x<<1, tree[x].deltat, tree[x].deltav, tree[x].deltatv);addone(x<<1|1, tree[x].deltat, tree[x].deltav, tree[x].deltatv);tree[x].deltat&＃61;tree[x].deltav&＃61;tree[x].deltatv&＃61;0;
}
void update(int x, int l, int r, int cl, int cr, int delta, int ty)
{if(cl<&＃61;l && r<&＃61;cr){if(ty) tree[x].deltat&＃43;&＃61;delta;else tree[x].deltatv&＃43;&＃61;tree[x].deltat*delta, tree[x].deltav&＃43;&＃61;delta;return;}down(x);int mid&＃61;(l&＃43;r)>>1;if(cl<&＃61;mid) update(x<<1, l, mid, cl, cr, delta, ty);if(cr>mid) update(x<<1|1, mid&＃43;1, r, cl, cr, delta, ty);
}
ll query(int x, int l, int r, int cx)
{if(l&＃61;&＃61;r) return tree[x].deltat*tree[x].deltav-tree[x].deltatv;down(x);int mid&＃61;(l&＃43;r)>>1;if(cx<&＃61;mid) return query(x<<1, l, mid, cx);else return query(x<<1|1, mid&＃43;1, r, cx);
}
inline void solve(int x, int y, int delta, int ty)
{int f1&＃61;top[x], f2&＃61;top[y];while(f1!&＃61;f2){if(d[f1]<d[f2]) swap(x, y), swap(f1, f2);update(1, 1, n, w[f1], w[x], delta, ty);x&＃61;fa[f1]; f1&＃61;top[x];}if(d[x]<d[y]) swap(x, y);update(1, 1, n, w[y], w[x], delta, ty);
}
int main()
{fread(buf, 1, sizeof(buf), stdin); read(n);for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;) read(fa[i]), add(fa[i], i);dfs1(1); dfs2(1, 1); read(m);for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;) read(ty), read(x), read(y), solve(1, x, y, ty-1);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) printf("%lld\n", query(1, 1, n, w[i]));
}