【传送门：51nod-1462】
简要题意：
给出一棵n个点的树，每个点有两个权值v,t
有Q个操作，有两种操作：
1.将x到根上的路径上的点的v值都加上d
2.将x到根上的路径上的点的t值都加上每个点的v值*d
最后求出所有点的t值
题解：
显然可以直接树链剖分做，不过lazy标记下放真麻烦，因为操作有互相影响
发现一种神标记方法——用矩阵
对于一个点，它的信息表示为$$ egin{matrix} 1 & 0 & 0 \ 0 & 1 & 0 \ v & t & 1 \ end{matrix} $$
而对于第一种操作，就将点的信息乘上$$ egin{matrix} 1 & 0 & 0 \ 0 & 1 & 0 \ d & 0 & 1 \ end{matrix} $$
而第二种操作则乘上$$ egin{matrix} 1 & d & 0 \ 0 & 1 & 0 \ 0 & 0 & 1 \ end{matrix} $$
这样就不用担心互相影响了，因为矩阵乘法满足结合律，所以直接将操作按顺序乘起来就行了
听说可以离线CDQ做
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; typedef long long LL; struct trnode { int l,r,lc,rc; }tr[210000];int trlen; struct Matrix { LL a[4][4]; Matrix() { memset(a,0,sizeof(a)); } }D[210000],cmp; Matrix multi(Matrix a,Matrix b) { Matrix c; for(int i=1;i<=3;i++) { for(int j=1;j<=3;j++) { for(int k=1;k<=3;k++) { c.a[i][j]+=a.a[i][k]*b.a[k][j]; } } } return c; } void bt(int l,int r) { trlen++;int now=trlen; tr[now].l=l;tr[now].r=r; D[now].a[1][1]=D[now].a[2][2]=D[now].a[3][3]=1; tr[now].lc=tr[now].rc=-1; if(l<r) { int mid=(tr[now].l+tr[now].r)/2; tr[now].lc=trlen+1;bt(l,mid); tr[now].rc=trlen+1,bt(mid+1,r); } } struct node { int x,y,next; }a[110000];int len,last[110000]; void ins(int x,int y){a[++len]=(node){x,y,last[x]};last[x]=len;} int son[110000],tot[110000]; void dfs1(int x) { tot[x]=1;son[x]=0; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; dfs1(y); if(tot[y]>tot[son[x]]) son[x]=y; tot[x]+=tot[y]; } } int top[110000],ys[110000],z; void dfs2(int x,int tp) { ys[x]=++z;top[x]=tp; if(son[x]!=0) dfs2(son[x],tp); for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=son[x]) dfs2(y,y); } } void update(int now) { int lc=tr[now].lc,rc=tr[now].rc; if(lc!=-1) D[lc]=multi(D[lc],D[now]); if(rc!=-1) D[rc]=multi(D[rc],D[now]); memset(D[now].a,0,sizeof(D[now].a)); D[now].a[1][1]=D[now].a[2][2]=D[now].a[3][3]=1; } void change(int now,int l,int r) { if(tr[now].l==l&&tr[now].r==r) { D[now]=multi(D[now],cmp); return ; } int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2; update(now); if(r<=mid) change(lc,l,r); else if(l>mid) change(rc,l,r); else change(lc,l,mid),change(rc,mid+1,r); } int fa[110000]; void solve(int x) { int tx=top[x]; while(x!=0) { change(1,ys[tx],ys[x]); x=fa[tx];tx=top[x]; } } LL d[110000]; void out(int now) { if(tr[now].l==tr[now].r) { d[tr[now].l]=D[now].a[3][2]; return ; } int lc=tr[now].lc,rc=tr[now].rc; update(now); if(lc!=-1) out(lc); if(rc!=-1) out(rc); } int main() { int n; scanf("%d",&n); len=0;memset(last,0,sizeof(last)); for(int i=2;i<=n;i++) { scanf("%d",&fa[i]); ins(fa[i],i); } dfs1(1); z=0;dfs2(1,1); trlen=0;bt(1,z); cmp.a[1][1]=cmp.a[2][2]=cmp.a[3][3]=1; int Q; scanf("%d",&Q); while(Q--) { int t,x;LL d; scanf("%d%d%lld",&t,&x,&d); if(t==1) cmp.a[1][2]=0,cmp.a[3][1]=d,solve(x); else cmp.a[3][1]=0,cmp.a[1][2]=d,solve(x); } out(1); for(int i=1;i<=n;i++) printf("%lld ",d[ys[i]]); return 0; }