[학습노트] MysC_K의 독립집 좋은 문제 - 동적 dp - 나무 해부 - 전역 균형 두 갈래 나무 - 학습 노트

제목 대의: 단점을 더하거나 1을 뿌리로 할 때 어떤 점의 자수의 최대 독립집을 구한다.문제풀이:'전역 균형 두 갈래 나무'라는 고급 조작을 배웠다.앞서 두 개의 로그를 발표하고 모든 겹사슬에 대해 단독으로 라인 트리를 열었다. 루거의 동적 dp 문제에서 한 로그보다 더 빨리 달렸고 강화판을 통과했다.
하나의 로그로 머리를 쓰다.아니면 두 개의 로그와 비슷한 방법으로 먼저 체인을 나누어 치료한 다음에 현재 우리는 라인 트리로 모든 무거운 체인을 유지하지 않는다.우리는 무거운 사슬의 각 점에 대해 가벼운 나무의size의 합을 구하고 +1을 구한 다음에 현재 사슬의 중심을 선택하여 나무를 세운다.이렇게 하면 각 점은 체인의 구간에 대응한다.이렇게 하는 장점은 매번 가벼운 테두리(두 개의 무거운 사슬을 연결하는 나무의 테두리로 볼 수 있음)를 지나갈 때마다size는 최소한 반을 줄일 수 있다는 것이다.건설된 나무의 한 변을 지나면 점이 중체인 구간에 대응하는 연결 블록의 크기도 적어도 반으로 줄어든다.따라서 매번 위로 뛰는 총 복잡도는 O(logn)이다.

#include
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define gc getchar()
#define debug(x) cerr<
#define sp <
#define ln <
using namespace std;
inline int inn()
{
	int x,ch,sgn=1;while(((ch=gc)<'0'||ch>'9')&&ch!='-');
	if(ch=='-') sgn=-1,x=0;else x=ch^'0';
	while((ch=gc)>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0');
	return x*sgn;
}
#define Max(a,b,c) max(max(a,b),c)
const int N=100010;
struct edges{
	int to,pre;
}e[N<<1];int h[N],etop,a[N],f[N],g[N],fq[N],gq[N],in[N],out[N],tms[N],dfc,fa[N],lst[N];
int top[N],sz[N],son[N],szq[N],bot[N];
inline int add_edge(int u,int v) { return e[++etop].to=v,e[etop].pre=h[u],h[u]=etop; }
namespace TREE_SPACE{
	int ncnt,fa[N],pre[N],suf[N],pos[N],lc[N],rc[N],id[N];
	struct node{
		int w00,w01,w10,w11;
		node() { w00=w01=w10=w11=0; }
		node(int f,int g) { w00=g,w11=f,w01=w10=0; }
		inline node operator+(const node &n)const
		{
			static node t;
			t.w00=Max(w00+n.w00,w00+n.w10,w01+n.w00);
			t.w01=Max(w00+n.w01,w00+n.w11,w01+n.w01);
			t.w10=Max(w10+n.w00,w10+n.w10,w11+n.w00);
			t.w11=Max(w10+n.w01,w10+n.w11,w11+n.w01);
			return t;
		}
		inline node operator+=(const node &n) { return (*this)=(*this)+n; }
		inline int f()const { return max(w10,w11); }
		inline int g()const { return max(w00,w01); }
		inline int ans()const { return max(f(),g()); }
		inline int show()const { debug(w00)sp,debug(w01)sp,debug(w10)sp,debug(w11)ln;return 0; }
	}val[N],s[N];
	inline int new_node(int f,int g)
	{
		int x=++ncnt;fa[x]=lc[x]=rc[x]=0;
		val[x]=s[x]=node(f,g);return x;
	}
	inline int push_up(int x)
	{
		s[x]=val[x];
		if(lc[x]) s[x]=s[lc[x]]+s[x];
		if(rc[x]) s[x]=s[x]+s[rc[x]];
		return 0;
	}
	inline int Build(int *f,int *g,int *sz,int l,int r)
	{
		int p=l;if(l>r) return 0;
		pre[l-1]=suf[r+1]=0;rep(i,l,r) pre[i]=pre[i-1]+sz[tms[i]];
		for(int i=r;i>=l;i--) suf[i]=suf[i+1]+sz[tms[i]];
		rep(i,l+1,r) if(max(pre[i-1],suf[i+1])<max(pre[p-1],suf[p+1])) p=i;
		int x=new_node(f[tms[p]],g[tms[p]]);pos[p]=x,id[x]=p;
		lc[x]=Build(f,g,sz,l,p-1),rc[x]=Build(f,g,sz,p+1,r);
		if(lc[x]) fa[lc[x]]=x;if(rc[x]) fa[rc[x]]=x;return push_up(x),x;
	}
	node Query(int x,int p)
	{
		if(id[x]<p) return Query(rc[x],p);
		node ans=val[x];if(rc[x]) ans+=s[rc[x]];
		if(p<id[x]) ans=Query(lc[x],p)+ans;return ans;
	}
	struct My_Tree{
		int rt;
		inline int build(int *f,int *g,int *sz,int l,int r) { return rt=Build(f,g,sz,l,r); }
		inline int query(int p) { return Query(rt,p).ans(); }
		inline int update(int p,int f,int g) { int x=pos[p];val[x]=node(f,g);while(x) push_up(x),x=fa[x];return 0; }
		inline int f() { return s[rt].f(); }
		inline int g() { return s[rt].g(); }
		inline int ans() { return s[rt].ans(); }
	}tr[N];
}
using TREE_SPACE::tr;
int fir_dfs(int x,int fa=0)
{
	for(int i=h[x],y;i;i=e[i].pre)
		if((y=e[i].to)^fa)
		{
			sz[x]+=fir_dfs(y,x);
			if(sz[y]>sz[son[x]]) son[x]=y;
		}
	return ++sz[x];
}
int sec_dfs(int x)
{
	fq[x]=a[x],gq[x]=0,tms[in[x]=++dfc]=x,szq[x]=1;
	if(son[x]) fa[son[x]]=x,top[son[x]]=top[x],sec_dfs(son[x]),bot[x]=bot[son[x]];else bot[x]=x;
	for(int i=h[x],y;i;i=e[i].pre) if((y=e[i].to)!=fa[x]&&e[i].to!=son[x])
		fa[y]=x,top[y]=y,sec_dfs(y),fq[x]+=g[y],gq[x]+=max(f[y],g[y]),szq[x]+=sz[y];
	if(son[x]) f[x]=fq[x]+g[son[x]],g[x]=gq[x]+max(f[son[x]],g[son[x]]);
	else f[x]=fq[x],g[x]=gq[x];return out[x]=dfc;
}
inline int upd(int x,int v)
{
	int cnt=0;for(int y=top[x];fa[y];y=top[fa[y]]) lst[++cnt]=y;
	for(int i=cnt,y,z;i;i--) y=lst[i],z=fa[y],
		tr[top[z]].update(in[z],fq[z]-=tr[y].g(),gq[z]-=tr[y].ans());
	tr[top[x]].update(in[x],fq[x]+=v,gq[x]);
	for(int y=top[x],z=fa[y];z;z=fa[y=top[z]])
		tr[top[z]].update(in[z],fq[z]+=tr[y].g(),gq[z]+=tr[y].ans());
	return 0;
}
char ss[3000010],tt[20];int ssl,ttl;
inline int show(int x)
{
	if(!x) ss[++ssl]='0';for(ttl=0;x;x/=10) tt[++ttl]=char(x%10+'0');
	for(;ttl;ttl--) ss[++ssl]=tt[ttl];return ss[++ssl]='
';
}
int main()
{
	int n=inn(),q=inn(),u,v,x;
	rep(i,2,n) u=inn(),v=inn(),add_edge(u,v),add_edge(v,u);
	rep(i,1,n) a[i]=inn();
	fir_dfs(1),top[1]=1,sec_dfs(1);
	rep(x,1,n) if(x==top[x]) tr[x].build(fq,gq,szq,in[x],in[bot[x]]);
	while(q--)
		if(inn()) x=inn(),upd(x,inn());
		else x=inn(),printf("%d
",tr[top[x]].query(in[x]));
	return fwrite(ss+1,sizeof(char),ssl,stdout),0;
}