[NOIP2018] 保卫王国

• 思路：
  DDP板题，就常规思路：\(f[i][0/1]\)表示（不）选i点,的最小代价。\(g[i][0/1]\)即对应的f除去son[v]的贡献
  然后利用\(g->f\)的转移退出矩阵转移式，利用结合率线段树维护即可。
• code:

#include
using namespace std;
const int N=1e6+5;
typedef long long ll;
int fa[N],n,m,rt,mod,nxt[N],to[N],head[N],ecnt;
ll b[N],f[N][2],g[N][2],inf=1e17,a[N];
void add_edge(int u,int v) {nxt[++ecnt]=head[u];to[ecnt]=v;head[u]=ecnt;}
struct matr {
	ll z1,z2,z3,z4;
	matr friend operator*(matr u,matr v) {
		matr w;
		w.z1=min(u.z1+v.z1,u.z2+v.z3),w.z2=min(u.z1+v.z2,u.z2+v.z4);
		w.z3=min(u.z3+v.z1,u.z4+v.z3),w.z4=min(u.z3+v.z2,u.z4+v.z4);
		return w;
	}
};
struct seg {int l,r;matr w;}T[N];
void P_up(int x){T[x].w=T[x<<1].w*T[x<<1|1].w;}
void _Give(matr &tmp,int p) {tmp.z3=tmp.z4=g[p][1],tmp.z2=g[p][0];}
void Build(int x,int l,int r) {
	T[x].l=l,T[x].r=r;
	if(l==r) {_Give(T[x].w,b[l]);T[x].w.z1=inf;return;}
	int mid=(l+r)>>1;
	Build(x<<1,l,mid),Build(x<<1|1,mid+1,r);
	P_up(x);
}
void Update(int x,int p,int y) {
	if(T[x].l==T[x].r) {_Give(T[x].w,y);return;}
	int mid=(T[x].l+T[x].r)>>1;
	if(p<=mid) Update(x<<1,p,y);
	else Update(x<<1|1,p,y);
	P_up(x);
}
matr Query(int x,int l,int r) {
	if(l<=T[x].l&&T[x].r<=r) {return T[x].w;}
	int mid=(T[x].l+T[x].r)>>1;
	matr val;bool f1=0;
	if(l<=mid) val=Query(x<<1,l,r),f1=1;
	if(r>mid) {
		if(f1)val=val*Query(x<<1|1,l,r);
		else val=Query(x<<1|1,l,r);
	}
	return val;
}
int sz[N],son[N],top[N],ed[N],dfn[N],Time,dep[N];
void gt_son(int x) {
	sz[x]=1;
	for(int i=head[x];i;i=nxt[i]) {
		int y=to[i];if(y==fa[x])continue;
		dep[y]=dep[x]+1;fa[y]=x;
		gt_son(y);sz[x]+=sz[y];
		if(sz[son[x]]=inf) printf("-1\n");
		else printf("%lld\n",ans);
		Change(A,-x),Change(B,-y);
	}
	return 0;
}