【传送门：51nod-1462】
简要题意：
给出一棵n个点的树，每个点有两个权值v,t
有Q个操作，有两种操作：
1.将x到根上的路径上的点的v值都加上d
2.将x到根上的路径上的点的t值都加上每个点的v值*d
最后求出所有点的t值
题解：
显然可以直接树链剖分做，不过lazy标记下放真麻烦，因为操作有互相影响
发现一种神标记方法——用矩阵
对于一个点，它的信息表示为$$ \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ v & t & 1 \\ \end{matrix} $$
而对于第一种操作，就将点的信息乘上$$ \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ d & 0 & 1 \\ \end{matrix} $$
而第二种操作则乘上$$ \begin{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[];int trlen;
struct Matrix
{
LL a[][];
Matrix()
{
memset(a,,sizeof(a));
}
}D[],cmp;
Matrix multi(Matrix a,Matrix b)
{
Matrix c;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
for(int k=;k<=;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[][]=D[now].a[][]=D[now].a[][]=;
tr[now].lc=tr[now].rc=-;
if(l<r)
{
int mid=(tr[now].l+tr[now].r)/;
tr[now].lc=trlen+;bt(l,mid);
tr[now].rc=trlen+,bt(mid+,r);
}
}
struct node
{
int x,y,next;
}a[];int len,last[];
void ins(int x,int y){a[++len]=(node){x,y,last[x]};last[x]=len;}
int son[],tot[];
void dfs1(int x)
{
tot[x]=;son[x]=;
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[],ys[],z;
void dfs2(int x,int tp)
{
ys[x]=++z;top[x]=tp;
if(son[x]!=) 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!=-) D[lc]=multi(D[lc],D[now]);
if(rc!=-) D[rc]=multi(D[rc],D[now]);
memset(D[now].a,,sizeof(D[now].a));
D[now].a[][]=D[now].a[][]=D[now].a[][]=;
}
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)/;
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+,r);
}
int fa[];
void solve(int x)
{
int tx=top[x];
while(x!=)
{
change(,ys[tx],ys[x]);
x=fa[tx];tx=top[x];
}
}
LL d[];
void out(int now)
{
if(tr[now].l==tr[now].r)
{
d[tr[now].l]=D[now].a[][];
return ;
}
int lc=tr[now].lc,rc=tr[now].rc;
update(now);
if(lc!=-) out(lc);
if(rc!=-) out(rc);
}
int main()
{
int n;
scanf("%d",&n);
len=;memset(last,,sizeof(last));
for(int i=;i<=n;i++)
{
scanf("%d",&fa[i]);
ins(fa[i],i);
}
dfs1();
z=;dfs2(,);
trlen=;bt(,z);
cmp.a[][]=cmp.a[][]=cmp.a[][]=;
int Q;
scanf("%d",&Q);
while(Q--)
{
int t,x;LL d;
scanf("%d%d%lld",&t,&x,&d);
if(t==) cmp.a[][]=,cmp.a[][]=d,solve(x);
else cmp.a[][]=,cmp.a[][]=d,solve(x);
}
out();
for(int i=;i<=n;i++) printf("%lld\n",d[ys[i]]);
return ;
}