动态dp初探

动态dp初探

动态区间最大子段和问题

给出长度为\(n\)的序列和\(m\)次操作，每次修改一个元素的值或查询区间的最大字段和（SP1714 GSS3）。

设\(f[i]\)为以下标\(i\)结尾的最大子段和，\(g[i]\)表示从起始位置到\(i\)以内的最大子段和。

\[f[i]=\max(f[i-1]+a[i],a[i])\\g[i]=\max(g[i-1],f[i])
\]

定义如下的矩阵乘法，显然这满足乘法结合律和分配律。

\[C=AB\\C[i,j]=\max_{k}(A[i,k]+B[k,j])
\]

将转移写为矩阵（注意\(g[i]=\max(g[i-1],f[i-1]+a[i],a[i])\)）

\[\begin{bmatrix}
f[i]\\
g[i]\\
0\end{bmatrix}
=
\begin{bmatrix}
a[i]&-\infty&a[i]\\
a[i]&0&a[i]\\
-\infty&-\infty&0\end{bmatrix}
\begin{bmatrix}
f[i-1]\\
g[i-1]\\
0\end{bmatrix}
\]

可知每个元素\(a[i]\)都对应了一个矩阵，可以认为区间\([l,r]​\)的答案所在矩阵正是

\[(\prod_{i=l}^k
\begin{bmatrix}
a[i]&-\infty&a[i]\\
a[i]&0&a[i]\\
-\infty&-\infty&0
\end{bmatrix}
)\begin{bmatrix}
0\\
-\infty\\
0\end{bmatrix}
\]

因此可以用线段树维护区间矩阵乘积。

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
const int inf=0x3f3f3f3f;

struct mtr {
	int a[3][3];
	int*operator[](int d) {return a[d];}
	inline mtr() {}
	inline mtr(int val) {
		a[0][0]=a[0][2]=a[1][0]=a[1][2]=val;
		a[0][1]=a[2][0]=a[2][1]=-inf;
		a[1][1]=a[2][2]=0;
	}
	mtr operator*(mtr b) {
		static mtr c;
		memset(&c,-inf,sizeof c);
		for(int i=0; i<3; ++i)
		for(int k=0; k<3; ++k)
		for(int j=0; j<3; ++j)
			c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
		return c;
	}
} t,a[N<<2];

#define ls (x<<1)
#define rs (x<<1|1)
void build(int x,int l,int r) {
	if(l==r) {
		scanf("%d",&r);
		a[x]=mtr(r);
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	a[x]=a[ls]*a[rs];
}
void modify(int x,int l,int r,int p,int val) {
	if(l==r) {
		a[x]=mtr(val);
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid) modify(ls,l,mid,p,val);
	else modify(rs,mid+1,r,p,val);
	a[x]=a[ls]*a[rs];
}
mtr query(int x,int l,int r,int L,int R) {
	if(L<=l&&r<=R) return a[x];
	int mid=(l+r)>>1;
	if(R<=mid) return query(ls,l,mid,L,R);
	if(mid<L) return query(rs,mid+1,r,L,R);
	return query(ls,l,mid,L,R)*query(rs,mid+1,r,L,R);
}

int main() {
	memset(&t,-inf,sizeof t); //notice
	t[0][0]=t[2][0]=0;
    int n,q;
	scanf("%d",&n);
	build(1,1,n);
	scanf("%d",&q);
	for(int op,l,r; q--; ) {
		scanf("%d%d%d",&op,&l,&r);
		if(op==0) modify(1,1,n,l,r);
		else {
			mtr ret=query(1,1,n,l,r)*t;
			printf("%d\n",max(ret[0][0],ret[1][0]));
		}
	}
	return 0;
}

动态树上最大权独立集

注意断句 给出一棵\(n​\)个节点树和\(m​\)次操作，每次操作修改一个点权并计算当前树上的最大权独立集的权值。

重链剖分，设\(y\)为\(x\)的某个儿子，\(s\)是重儿子，\(f[x,t]\)表示在以\(x\)为根的子树中不选/选\(x\)时的最大权独立集权值，\(g[x,t]\)表示在以\(x\)的为根的子树中除去以\(s\)为根的子树部分内不选/选\(x\)的最大权独立集权值，。

\[g[x,0]=\sum_{y\not=s}\max(f[y,0],f[y,1])\\
g[x,1]=a[x]+\sum_{y\not=s} f[y,0]\\
f[x,0]=g[x,0]+\max(f[s,0],f[s,1])\\
f[x,1]=g[x,1]+f[s,0]
\]

然后改写为矩阵乘法

\[\begin{bmatrix}
f[x,0]\\
f[x,1]
\end{bmatrix}=
\begin{bmatrix}
g[x,0]&g[x,0]\\
g[x,1]&-\infty
\end{bmatrix}
\begin{bmatrix}
f[s,0]\\
f[s,1]
\end{bmatrix}
\]

当\(s\)不存在时，钦定\(f[s,0]=0\)、\(f[s,1]=-\infty\)。进一步可发现在一条链内，链顶的\(f[,t]​\)值正是链上所有的“G矩阵”（应该明白指的是那个吧）乘起来的第一列值。

因此我们可以树剖维护重链上这些矩阵的乘积，更新时从修改点跳到每条重链的链顶，计算链顶部\(f[,t]\)，更新他父亲的\(g[,t]\)（显然他不是父亲的重儿子）,然后再跳往父亲所在重链……。

也可以lct来做，（试了一下树剖发现麻烦爆了）每次access修改点到根，然后对这部分重计算就好了。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;

struct mtr {
	int a[2][2];
	int*operator[](int d) {return a[d];}
	mtr() {memset(a,-inf,sizeof a);}
	mtr operator*(mtr b) {
		mtr c;
		for(int i=0; i<2; ++i)
		for(int k=0; k<2; ++k)
		for(int j=0; j<2; ++j)
			c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
		return c;
	}
} G[N],PG[N]; 

int n,m,a[N];
int head[N],to[N<<1],last[N<<1];
int fa[N],ch[N][2],dp[N][2];

void add_edge(int x,int y) {
	static int cnt=0;
	to[++cnt]=y,last[cnt]=head[x],head[x]=cnt;
}
void dfs(int x) {
	dp[x][1]=a[x];
	for(int i=head[x]; i; i=last[i]) {
		if(to[i]==fa[x]) continue;
		fa[to[i]]=x;
		dfs(to[i]);
		dp[x][0]+=max(dp[to[i]][0],dp[to[i]][1]);
		dp[x][1]+=dp[to[i]][0];
	}
	G[x][0][0]=G[x][0][1]=dp[x][0];
	G[x][1][0]=dp[x][1];
	PG[x]=G[x];
}
void update(int x) {
	PG[x]=G[x];
	if(ch[x][0]) PG[x]=PG[ch[x][0]]*PG[x]; //无交换律
	if(ch[x][1]) PG[x]=PG[x]*PG[ch[x][1]];
}
int get(int x) {
	return ch[fa[x]][0]==x?0:(ch[fa[x]][1]==x?1:-1);
}
void rotate(int x) {
	int y=fa[x],k=get(x);
	if(~get(y)) ch[fa[y]][get(y)]=x;
	fa[x]=fa[y];
	fa[ch[y][k]=ch[x][k^1]]=y;
	fa[ch[x][k^1]=y]=x;
	update(y);
	update(x);
}
void splay(int x) {
	while(~get(x)) {
		int y=fa[x];
		if(~get(y)) rotate(get(x)^get(y)?x:y);
		rotate(x);
	}
}
void access(int x) {
	for(int y=0; x; x=fa[y=x]) {
		splay(x);
		if(ch[x][1]) { //旧的重儿子
			G[x][0][0]+=max(PG[ch[x][1]][0][0],PG[ch[x][1]][1][0]);
			G[x][1][0]+=PG[ch[x][1]][0][0];
		}
		if(y) { //新的重儿子
			G[x][0][0]-=max(PG[y][0][0],PG[y][1][0]);
			G[x][1][0]-=PG[y][0][0];
		}
		G[x][0][1]=G[x][0][0]; //别忘了
		ch[x][1]=y;
		update(x);
	}
}
void modify(int x,int y) {
	access(x);
	splay(x);
	G[x][1][0]+=y-a[x];
	update(x);
	a[x]=y;
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; ++i) scanf("%d",a+i);
	for(int x,y,i=n; --i; ) {
		scanf("%d%d",&x,&y);
		add_edge(x,y);
		add_edge(y,x);
	}
	dfs(1); //所有连边是轻边
	for(int x,y; m--; ) {
		scanf("%d%d",&x,&y);
		modify(x,y);
		splay(1);
		printf("%d\n",max(PG[1][0][0],PG[1][1][0]));
	}
	return 0;
}

全局平衡二叉树

然后讲一讲这道题的毒瘤加强版。传送门

数据加强并且经过特殊构造，树剖和LCT都过不了了。树剖本身复杂度太大， O(\(m\log^2n\))过不了百万是很正常的；而LCT虽然只有一个\(\log\) ，但由于常数过大也被卡了。

树剖的两个 \(\log\) 基本上可以放弃治疗了。但是我们不禁要问，LCT究竟慢在哪里？

仔细想想，LCT的access复杂度之所以是一个 \(\log​\) ，是由于splay的势能分析在整棵LCT上依然成立，也就是说可以把LCT看作一棵大splay，在这棵大splay上的一次access只相当于一次splay。

话虽然是这么说，但是实际上当我们不停地随机access的时候，要调整的轻重链数量还是很多的。感受一下，拿极端情形来说，如果树是一条链，一开始全是轻边，那么对链末端的结点access一次显然应该是 \(O(n)\)的。所以其实LCT的常数大就大在它是靠势能法得到的 \(O(\log n)\)，这么不靠谱的玩意是容易gg的。

但是如果我们不让LCT放任*地access，而是一开始就给它构造一个比较优雅的姿态并让它静止（本来这棵树也不需要动），那么它也许就有救了。我们可以按照树链剖分的套路先划分出轻重边，然后对于重链建立一棵形态比较好的splay，至于轻儿子就跟原来的LCT一样直接用轻边挂上即可。什么叫“形态比较好”呢？我们给每个点 \(x​\) 定义其权重为 size[x]-size[son[x]]，其中 son[x] 是它的重儿子，那么对于一条重链，我们可以先找到它的带权重心作为当前节点，然后对左右分别递归建树。

by GKxx blog

似乎较lct常数更小，也蛮好些的。

#include <bits/stdc++.h>
using namespace std;

namespace IO { // 卡着时限过
	const unsigned Buffsize=1<<24,Output=1<<24;
	static char Ch[Buffsize],*St=Ch,*T=Ch;
	inline char getc() {
		return((St==T)&&(T=(St=Ch)+fread(Ch,1,Buffsize,stdin),St==T)?0:*St++);
	}
	static char Out[Output],*nowps=Out;
	inline void flush() {
		fwrite(Out,1,nowps-Out,stdout);
		nowps=Out;
	}
	template<typename T>inline void read(T&x) {
		x=0;
		static char ch;
		T f=1;
		for(ch=getc(); !isdigit(ch); ch=getc())if(ch=='-')f=-1;
		for(; isdigit(ch); ch=getc())x=x*10+(ch^48);
		x*=f;
	}
	template<typename T>inline void write(T x,char ch='\n') {
		if(!x)*nowps++=48;
		if(x<0)*nowps++='-',x=-x;
		static unsigned sta[111],tp;
		for(tp=0; x; x/=10)sta[++tp]=x%10;
		for(; tp; *nowps++=sta[tp--]^48);
		*nowps++=ch;
		flush();
	}
}
using IO::read;
using IO::write;

const int N=1e6+10;
const int inf=0x3f3f3f3f;

struct mtr {
	int a[2][2];
	int*operator[](int x) {return a[x]; }
	inline mtr() {}
	inline mtr(int g0,int g1) {
		a[0][0]=a[0][1]=g0;
		a[1][0]=g1;
		a[1][1]=-inf;
	}
	inline mtr operator*(mtr b) {
		mtr c;
		c[0][0]=max(a[0][0]+b[0][0],a[0][1]+b[1][0]);
		c[0][1]=max(a[0][0]+b[0][1],a[0][1]+b[1][1]);
		c[1][0]=max(a[1][0]+b[0][0],a[1][1]+b[1][0]);
		c[1][1]=max(a[1][0]+b[0][1],a[1][1]+b[1][1]);
		return c;
	}
};

int n,m,a[N];
int head[N],to[N<<1],last[N<<1];
int siz[N],son[N],g[N][2];
inline void add_edge(int x,int y) {
	static int cnt=0;
	to[++cnt]=y,last[cnt]=head[x],head[x]=cnt;
}
void dfs1(int x,int pa) {
	siz[x]=1;
	g[x][1]=a[x];
	for(int i=head[x]; i; i=last[i]) {
		if(to[i]==pa) continue;
		dfs1(to[i],x);
		siz[x]+=siz[to[i]];
		if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
		g[x][0]+=max(g[to[i]][0],g[to[i]][1]);
		g[x][1]+=g[to[i]][0];
	}
}
void dfs2(int x,int pa) {
	if(!son[x]) return;
	g[x][0]-=max(g[son[x]][0],g[son[x]][1]);
	g[x][1]-=g[son[x]][0];
	for(int i=head[x]; i; i=last[i])
		if(to[i]!=pa) dfs2(to[i],x);
}

mtr G[N],PG[N];
int root,fa[N],ch[N][2];
int stk[N],tp;
bool is_root[N];

inline void update(int x) {
	PG[x]=G[x];
	if(ch[x][0]) PG[x]=PG[ch[x][0]]*PG[x];
	if(ch[x][1]) PG[x]=PG[x]*PG[ch[x][1]];
}
int chain(int l,int r) {
	if(r<l) return 0;
	int sum=0,pre=0;
	for(int i=l; i<=r; ++i) sum+=siz[stk[i]]-siz[son[stk[i]]];
	for(int i=l; i<=r; ++i) {
		pre+=siz[stk[i]]-siz[son[stk[i]]];
		if((pre<<1)>=sum) {
			int x=stk[i];
			ch[x][0]=chain(l,i-1);
			ch[x][1]=chain(i+1,r);
			if(ch[x][0]) fa[ch[x][0]]=x;
			if(ch[x][1]) fa[ch[x][1]]=x;
			update(x);
			return x;
		}
	}
	return 2333;
}
int tree(int top,int pa) {
	for(int x=top; x; x=son[pa=x]) {
		for(int i=head[x]; i; i=last[i]) {
			if(to[i]!=son[x]&&to[i]!=pa) {
				fa[tree(to[i],x)]=x;
			}
		}
		G[x]=mtr(g[x][0],g[x][1]);
	}
	tp=0;
	for(int x=top; x; x=son[x]) stk[++tp]=x;
	return chain(1,tp);
}
inline void build() {
	root=tree(1,0);
	for(int i=1; i<=n; ++i) {
		is_root[i]=ch[fa[i]][0]!=i&&ch[fa[i]][1]!=i;
	}
}
inline int solve(int x,int y) {
	g[x][1]+=y-a[x];
	a[x]=y;
	for(int f0,f1; x; x=fa[x]) {
		f0=PG[x][0][0];
		f1=PG[x][1][0];
		G[x]=mtr(g[x][0],g[x][1]);
		update(x);
		if(fa[x]&&is_root[x]) {
			g[fa[x]][0]+=max(PG[x][0][0],PG[x][1][0])-max(f0,f1);
			g[fa[x]][1]+=PG[x][0][0]-f0;
		}
	}
	return max(PG[root][0][0],PG[root][1][0]);
}

int main() {
	read(n);
	read(m);
	for(int i=1; i<=n; ++i) read(a[i]);
	for(int x,y,i=n; --i; ) {
		read(x);
		read(y);
		add_edge(x,y);
		add_edge(y,x);
	}
	dfs1(1,0);
	dfs2(1,0);
	build();
	int lastans=0;
	for(int x,y; m--; ) {
		read(x);
		read(y);
		x^=lastans;
		lastans=solve(x,y);
		write(lastans);
	}
	return 0;
}

NOIP18 保卫王国

给出一棵\(n​\)个节点树和\(m​\)次询问，每次询问强制选/不选两个点然后计算当前树上的最小覆盖集，询问互相独立。

提示：强制选一个点就是把它的点权改成0，强制不选就是改成 \(\infty\)；最小覆盖权值+最大独立集权值=总权值。

// 省略了一些函数
// O2下速度还不错
// 注意long long
const int N=1e6+10;
const long long inf=1e10;

......

long long tot,res;
inline void solve(int x,long long y) {
	tot+=y;
	g[x][1]+=y;
	for(long long f0,f1; x; x=fa[x]) {
		f0=PG[x][0][0];
		f1=PG[x][1][0];
		G[x]=mtr(g[x][0],g[x][1]);
		update(x);
		if(fa[x]&&is_root[x]) {
			g[fa[x]][0]+=max(PG[x][0][0],PG[x][1][0])-max(f0,f1);
			g[fa[x]][1]+=PG[x][0][0]-f0;
		}
	}
}
inline void solve(int x,int p,int y,int q) {
	long long sx,sy;
	if(!p&&!q) sx=inf,sy=inf,res=0;
	else if(!p&&q) sx=inf,sy=0,res=a[y];
	else if(p&&!q) sx=0,sy=inf,res=a[x];
	else sx=0,sy=0,res=a[x]+a[y];
	solve(x,sx-a[x]);
	solve(y,sy-a[y]);
	res+=tot-max(PG[root][0][0],PG[root][1][0]);
	solve(x,a[x]-sx);
	solve(y,a[y]-sy);
}

char type[10];
int main() {
	scanf("%d%d%s",&n,&m,type);
	for(int i=1; i<=n; ++i) {
		scanf("%lld",a+i);
		tot+=a[i];
	}
	for(int x,y,i=n; --i; ) {
		scanf("%d%d",&x,&y);
		add_edge(x,y);
		add_edge(y,x);
	}
	dfs1(1,0);
	dfs2(1,0);
	build();
	for(int x,p,y,q; m--; ) {
		scanf("%d%d%d%d",&x,&p,&y,&q);
		if(!p&&!q&&(prt[x]==y||prt[y]==x)) {
			puts("-1");
			continue;
		}
		solve(x,p,y,q);
		printf("%lld\n",res);
	}
	return 0;
}

bzoj4911 [Sdoi2017]切树游戏

留坑。

bzoj4721 洪水

给出一棵\(n\)个节点的树以及\(m\)次操作，每次操作修改删除某一个点的代价，或者查询删除一些点使得节点\(x​\)不与其子树中任意叶节点联通的最小代价和。

重链剖分，设\(y​\)为\(x​\)的某个儿子，\(s​\)是重儿子，\(f[x]​\)表示在以\(x​\)为根的子树时的解，​\(g[x]=\sum_{y\not=s}f[y]​\)。当\(x​\)是叶节点时，\(g[x]=+\infty​\)，\(f[x]=a[x]​\)。一般转移为\(f[x]=\min(a[x],g[x]+f[s])​\)。

使用变换\(T(a,b)(v)\)表示一个转移\(\min(a,v+b)\)，​变换的合并为

\[\begin{aligned}
T(a,b)(T(c,d)(v))
&=\min(a,\min(c,v+d)+b)\\
&=\min(a,c+b,v+d+b)&(\star)\\
&=\min(\min(a,c+b),v+(d+b))\\
&=T(\min(a,c+b),d+b)(v)
\end{aligned}
\]

思考\((\star)\)的意义。同“动态树上最大权独立集”类似的处理，节点\(x\)对应着一个变换\(T(a[x],g[x])(v)\)，那么子树\(x\)的答案\(f[x]\)为\(x\)到\(x\)所在重链的底上所有变换从后往前的并作用在\(0\)上的值。

仍然使用全局平衡二叉树来维护。

来自copier的怨念

关于统计答案，首先得知道辅助树上\(ch[x,1]\)指向\(x\)管辖范围\([l,r]\)内的后一半即\([x+1,r]\)这一段，所以我们可以从\(x\)出发，记录\(R\)为已经得到了\([x,R]\)的贡献，加上\(ch[x,1]\)这段的贡献，然后不断跳\(fa[x]\)直到\(x=R+1\)，接着统计并更新\(R\)。当\(R\)到达链底时结束。

一个巧妙地实现是不需要记录\(R​\)，每次在链内向上跳\(fa[x]​\)时，如果\(ch[fa[x],0]==x​\)，就统计\(ch[fa[x],1]​\)地贡献。显然这样也能达到同样的效果。

再补充。0看作时所有叶子节点的轻儿子，设其中一个叶子节点为\(l\)。

\[\text{set}
\begin{cases}
g[0]=0\\
a[0]=+\infty\\
f[0]=+\infty\\
\end{cases}
\rightarrow
\begin{cases}
g[l]=f[0]=+\infty\\
f[l]=\min(a[l],0+g[l])=a[l]
\end{cases}
\]

所以强令\(a[0]=f[0]=+\infty\)，就能使所有的叶子节点初始化。

关于答案输出需要留意每个叶子节点的第二个参数是\(+\infty\)结合变换合并的公式可知最终得到的合变换内第二个参数无穷大，所以答案是第一个参数。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6+10;
const LL inf=1e14;

struct trans {
	LL a,b;
	inline trans() {}
	inline trans(LL a,LL b):a(a),b(b){}
	inline trans calc(trans t) {
		return trans(min(a,t.a+b),t.b+b);
	}
} T[N],PT[N];

int n,m;
LL a[N],f[N];
int siz[N],son[N],head[N],to[N<<1],last[N<<1];

inline void add_edge(int x,int y) {
	static int cnt=0;
	to[++cnt]=y,last[cnt]=head[x],head[x]=cnt;
}
int ch[N][2],fa[N],stk[N],tp;
bool irt[N];
inline void update(int x) {
	PT[x]=PT[ch[x][0]].calc(T[x].calc(PT[ch[x][1]]));
}
int chain(int l,int r) {
	if(l>r) return 0;
	int sum=0,pre=0,x;
	for(int i=l; i<=r; ++i) sum+=siz[stk[i]]-siz[son[stk[i]]];
	for(int i=l; i<=r; ++i) {
		pre+=siz[stk[i]]-siz[son[stk[i]]];
		if((pre<<1)>=sum) {
			x=stk[i];
			fa[ch[x][0]=chain(l,i-1)]=x;
			fa[ch[x][1]=chain(i+1,r)]=x;
			update(x);
			break;
		}
	}
	return x;
}
int build(int x) {
	for(tp=0; x; x=son[x]) stk[++tp]=x;
	irt[x=chain(1,tp)]=1;
	return x;
}
void dfs(int x) {
	siz[x]=1;
	for(int i=head[x]; i; i=last[i]) {
		if(to[i]==fa[x]) continue;
		fa[to[i]]=x;
		dfs(to[i]);
		f[x]+=f[to[i]];
		siz[x]+=siz[to[i]];
		if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
	}
	if(son[x]) {
		T[x]=trans(a[x],f[x]-f[son[x]]);
		f[x]=min(f[x],a[x]);
	} else {
		T[x]=trans(a[x],inf);
		f[x]=a[x];
	}
	for(int i=head[x]; i; i=last[i]) {
		if(to[i]!=fa[x]&&to[i]!=son[x])
			fa[build(to[i])]=x;
	}
}

int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) scanf("%lld",a+i);
	for(int x,y,i=n; --i; ) {
		scanf("%d%d",&x,&y);
		add_edge(x,y);
		add_edge(y,x);
	}
	PT[0]=trans(inf,0); //
	dfs(1), fa[build(1)]=0;
  /*for(int i=0; i<=n; ++i)
	cout<<T[i].a<<' '<<T[i].b<<' '<<PT[i].a<<' '<<PT[i].b<<endl;
	cout<<endl;
    */
	scanf("%d",&m);
	while(m--) {
		static char op[10];
		static int x,y;
		scanf("%s%d",op,&x);
		if(op[0]=='Q') {
			trans ans=T[x].calc(PT[ch[x][1]]);
			for(; !irt[x]; x=fa[x]) {
				if(ch[fa[x]][0]==x) ans=ans.calc(T[fa[x]].calc(PT[ch[fa[x]][1]]));
			}
			printf("ans is %lld\n",ans.a);
		} else {
			scanf("%d",&y);
			T[x].a+=y;
			for(; x; x=fa[x]) {
				if(irt[x]) T[fa[x]].b-=PT[x].a;
				update(x);
				if(irt[x]) T[fa[x]].b+=PT[x].a;
			}
		}
	}
	return 0;
}