思路：

注意到是动态求树上最小权覆盖集。

其等价于全集减去最大权独立集。

故考虑求出最大权独立集，考虑动态规划算法，设 $f_{i, 0/1}$ 表示 $i$ 子树内不选 $i$ 和选 $i$ 的最大权独立集的权值。

容易得到状态转移方程：

$$f_{i, 0} = \sum_{j \in son_i} \max(f_{j, 0}, f_{j, 1})$$$$f_{i, 1} = a_i + \sum_{j \in son_i} f_{j, 0}$$

然后本题还有限制是必选/不能选某些点；若 $x$ 必选，则将 $x$ 的权值修改为 $-10^{10}$，否则修改为 $10^{10}$。

我们需要支持单点修改，查询 $\max(f_{1, 0}, f_{1, 1})$，朴素实现是 $O(nq)$ 的。

考虑重链剖分优化，设 $g_{i, 0}$ 表示对于 $i$ 的所有轻儿子可取可不取的最大独立集的权值，$g_{i, 1}$ 表示对于 $i$ 的所有轻儿子都不取的最大独立集的权值。

则状态转移方程优化为：

$$f_{i, 0} = g_{i, 0} + \max(f_{son_i, 0},f_{son_i, 1})$$$$f_{i, 1} = a_i + g_{i, 1} + f_{son_i, 0}$$

发现这里多出来个 $a_i$ 很烦，考虑直接揉进 $g_{i, 1}$ 中（将定义改为取自己且所有轻儿子都不取的权值）。

容易发现我们进行单点修改，改变的 $g$ 只有每条重链顶端节点的父亲。

那么如何考虑求 $f$ 呢？

注意到：

$$f_{i, 0} = g_{i, 0} + \max(f_{son_i, 0},f_{son_i, 1})$$$$f_{i, 1} = g_{i, 1} + f_{son_i, 0}$$

这个递推式子只和 $i$ 和 $son_i$ 相关，故考虑放到一条重链上去。

考虑使用广义的 $\max+$ 矩阵，即：

$$C_{i, j} = \max_{k = 1}^n A_{i, k} + B_{k, j}$$

容易证明其存在结合律。

故考虑由：

$$\begin{vmatrix} f_{son_i, 0} & f_{son_i, 1} \end{vmatrix} \times T_i = \begin{vmatrix} f_{i, 0} & f_{i, 1} \end{vmatrix}$$

由递推公式可以得到：

$$T_i = \begin{vmatrix} g_{i, 0} & g_{i, 1}\\ g_{i, 0} & -\inf\end{vmatrix}$$

故使用线段树维护区间矩阵的乘积，然后重链剖分即可。

时间复杂度为 $O(N \log^2 N)$。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100100,M=2,INF=1e17;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
ll n,m,X,Y,x,y,cnt,sum,ans;
ll a[N],dp[N][2],g[N][2],fa[N],p[N],t[N],z[N],d[N];
ll A[N],B[N],C[N];
vector<ll> E[N];
string s;
class Mat{
public:
	ll a[M][M];
	ll* operator[](ll i){
		return a[i];
	}
	Mat(){
        for(int i=0;i<M;i++)
          for(int j=0;j<M;j++)
            a[i][j]=-INF;
	}
    Mat operator*(Mat rhs)const{
		Mat ans;
		for(int i=0;i<M;i++)
		  for(int j=0;j<M;j++)
		    for(int k=0;k<M;k++)
		      ans[i][j]=max(ans[i][j],a[i][k]+rhs[k][j]);
		return ans;
	}
    Mat operator+(Mat rhs)const{
		Mat ans;
		for(int i=0;i<M;i++)
		  for(int j=0;j<M;j++)
		    ans[i][j]=max(a[i][j],rhs[i][j]);
		return ans;
	}
}H[N];
class Tree{
public:
	struct Node{
		ll l,r;
		Mat data;
	}X[N<<2];
	void pushup(ll k){
		X[k].data=X[k<<1].data*X[k<<1|1].data;
	}
	void build(ll k,ll l,ll r){
		X[k].l=l,X[k].r=r;
		if(l==r){
			X[k].data[0][0]=X[k].data[0][1]=g[B[l]][0];
			X[k].data[1][0]=g[B[l]][1];
			H[l]=X[k].data;
			return ;
		}
		ll mid=(l+r)>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
		pushup(k);
	}
	void add(ll k,ll i){
		if(X[k].l==i&&i==X[k].r){
//			puts("-1");
			X[k].data=H[i];
			return ;
		}
		ll mid=(X[k].l+X[k].r)>>1;
		if(i<=mid)
		  add(k<<1,i);
		else
		  add(k<<1|1,i);
		pushup(k);
	}
	Mat qurey(ll k,ll l,ll r){
		if(X[k].l==l&&r==X[k].r)
		  return X[k].data;
		ll mid=(X[k].l+X[k].r)>>1;
		if(r<=mid)
		  return qurey(k<<1,l,r);
		else if(l>mid)
		  return qurey(k<<1|1,l,r);
		else
		  return qurey(k<<1,l,mid)*qurey(k<<1|1,mid+1,r);
	}
	Mat qurey(ll u){
		return qurey(1,A[u],C[u]);
	}
}T;
void add(ll u,ll v){
	E[u].push_back(v);
	E[v].push_back(u);
}
void dfs1(ll u,ll f){
	dp[u][1]=a[u];
	p[u]=1;
	for(auto v:E[u]){
		if(v==f)
		  continue;
		fa[v]=u;
		d[v]=d[u]+1;
		dfs1(v,u);
		dp[u][0]+=max(dp[v][0],dp[v][1]);
		dp[u][1]+=dp[v][0]; 
		p[u]+=p[v];
		if(p[v]>p[z[u]])
		  z[u]=v;
	}
}
void dfs2(ll u,ll k){
	g[u][1]=a[u];
	A[u]=++cnt;
	B[cnt]=u;
	C[k]=max(C[k],cnt);
	t[u]=k;
	if(!z[u])
	  return ;
	dfs2(z[u],k);
	for(auto v:E[u]){
		if(v==fa[u]||v==z[u])
		  continue;
		dfs2(v,v);
		g[u][0]+=max(dp[v][0],dp[v][1]);
		g[u][1]+=dp[v][0];
	}
}
void updata(ll u,ll v){
	Mat x,y;
	H[A[u]][1][0]+=v;
	a[u]+=v;
	while(u){
		x=T.qurey(t[u]);
		T.add(1,A[u]);
		y=T.qurey(t[u]);
		u=fa[t[u]];
		H[A[u]][0][0]+=max(y[0][0],y[1][0])-max(x[0][0],x[1][0]);
		H[A[u]][0][1]=H[A[u]][0][0];
		H[A[u]][1][0]+=y[0][0]-x[0][0];
//		cerr<<H[A[u]][0][0]<<' '<<H[A[u]][0][1]<<' '<<H[A[u]][1][0]<<'\n';
	}
}
int main(){
	n=read(),m=read(),cin>>s;
	for(int i=1;i<=n;i++){
		a[i]=read();
		ans+=a[i];
	}
	for(int u,v,i=1;i<n;i++){
		u=read(),v=read();
		add(u,v);
	}
	dfs1(1,1);
	dfs2(1,1);
	T.build(1,1,cnt);
//	for(int i=1;i<=n;i++){
//		write(B[i]);
//		putchar(' ');
//	}
//	putchar('\n');
	while(m--){
		X=read(),x=read(),Y=read(),y=read();
        if((fa[X]==Y||fa[Y]==X)&&!x&&!y){
            puts("-1");
            continue;
        }
		updata(X,x?-1e10:1e10);
		updata(Y,y?-1e10:1e10);
		auto t=T.qurey(1);
		sum=ans-max(t[0][0],t[1][0])+(x?0:1e10)+(y?0:1e10);
        write(sum);
        putchar('\n');
        updata(X,x?1e10:-1e10);
		updata(Y,y?1e10:-1e10);
	}
	return 0;
}

这是一年前写的 code 了，码风可能有点不好看，见谅。

C74 动态DP+树剖 P5024 [NOIP2018 提高组] 保卫王国

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define int long long
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)
const int N=100005,inf=1e18;
int n,m,p[N],all;
vector<int>G[N];
int fa[N],siz[N],son[N],f[N][2];
int dfn[N],id[N],top[N],bot[N],tot;
//dfn:dfs序,id:节点编号,top:链头节点,bot:链尾序号

void dfs(int x){ //树剖f,fa,siz,son
  f[x][0]=0; f[x][1]=p[x];
  siz[x]=1;
  for(int y:G[x]){
    if(y==fa[x]) continue;
    fa[y]=x;
    dfs(y);
    f[x][0]+=max(f[y][0],f[y][1]);
    f[x][1]+=f[y][0];    
    siz[x]+=siz[y];
    
    if(siz[y]>siz[son[x]]) son[x]=y;
  }
}
void dfs(int x,int tp){ //树剖dfn,id,top,bot
  dfn[x]=++tot;id[tot]=x;top[x]=tp;bot[tp]=tot;
  if(son[x]) dfs(son[x],tp);
  for(auto y:G[x]){
    if(y==fa[x]||y==son[x]) continue;
    dfs(y,y);
  }
}

struct matrix{
  int g[2][2];
  matrix operator*(matrix b){ //广义矩阵乘积
    matrix t; 
    t.g[0][0]=t.g[0][1]=t.g[1][0]=t.g[1][1]=-inf;
    for(int i=0; i<=1; ++i)
    for(int j=0; j<=1; ++j)
    for(int k=0; k<=1; ++k)
      t.g[i][j]=max(t.g[i][j],g[i][k]+b.g[k][j]);
    return t;
  }  
}mt[N],tr[N<<2];//节点g矩阵,线段树g矩阵及乘积 

void build(int u,int l,int r){ //建线段树
  if(l==r){
    int x=id[l],g0=0,g1=p[x]; //g0不选x，g1选x
    for(auto y:G[x])
      if(y!=fa[x]&&y!=son[x])
        g0+=max(f[y][0],f[y][1]), //g0选或不选y
        g1+=f[y][0]; //g1不选y
    tr[u]=mt[x]={g0,g0,g1,-inf};
    return;
  }
  build(ls,l,mid);
  build(rs,mid+1,r);
  tr[u]=tr[ls]*tr[rs]; //g矩阵乘积
}
void change(int u,int l,int r,int p){ //点修
  if(l==r){tr[u]=mt[id[l]]; return;}
  if(p<=mid) change(ls,l,mid,p);
  else change(rs,mid+1,r,p);
  tr[u]=tr[ls]*tr[rs];
}
matrix query(int u,int l,int r,int x,int y){ //区查
  if(x==l&&r==y) return tr[u];
  if(y<=mid) return query(ls,l,mid,x,y);
  if(x>mid) return query(rs,mid+1,r,x,y);
  return query(ls,l,mid,x,mid)*query(rs,mid+1,r,mid+1,y);
}void update(int u,int v){ //修改点权
  mt[u].g[1][0]+=v-p[u]; p[u]=v;
  
  while(u){
    matrix a=query(1,1,n,dfn[top[u]],bot[top[u]]);
    change(1,1,n,dfn[u]);
    matrix b=query(1,1,n,dfn[top[u]],bot[top[u]]);
    u=fa[top[u]]; //跳到链头的父节点
    mt[u].g[0][0]+=max(b.g[0][0],b.g[1][0])
                  -max(a.g[0][0],a.g[1][0]);
    mt[u].g[0][1]=mt[u].g[0][0];
    mt[u].g[1][0]+=b.g[0][0]-a.g[0][0];
  }
}
signed main(){
  scanf("%lld%lld",&n,&m);string s;cin>>s;
  for(int i=1;i<=n;i++)scanf("%lld",&p[i]),all+=p[i];
  for(int i=1,x,y;i<n;i++){
    scanf("%lld%lld",&x,&y);
    G[x].push_back(y); G[y].push_back(x);
  }
  dfs(1);dfs(1,1); //树链剖分
  build(1,1,n);    //建线段树
  while(m--){
    int a,x,b,y;
    scanf("%lld%lld%lld%lld",&a,&x,&b,&y);
    if(x==0&&y==0&&(fa[a]==b||fa[b]==a))
      {puts("-1"); continue;} //无解
    //覆盖集选则独立集不选,覆盖集不选则独立集必选      
    int va=p[a],vb=p[b];
    update(a,x?-inf:inf); update(b,y?-inf:inf);
    matrix t=query(1,1,n,dfn[1],bot[1]);
    int s=max(t.g[0][0],t.g[1][0]);
    s+=x?0:va-inf; 
    s+=y?0:vb-inf;
    printf("%lld\n",all-s);
    
    update(a,va); update(b,vb);
  }
}