Description：

求一棵树的最小权点覆盖，每次指定两个点要求他们必须选或不选。

$1\leqslant n\leqslant 10^5$

Solution1：

树的最小权点覆盖可以树形 $DP$ ，还要修改那就动态 $DP$ ，每次把两个点的权值改成 $\infty$ 或者 $-\infty$ 。

Code1：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int fa[MAXN],siz[MAXN],son[MAXN],dep[MAXN],top[MAXN],bot[MAXN];

int rnk[MAXN],th[MAXN],tot = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth;siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;rnk[k] = ++tot;th[tot] = k;

	if(son[k] == 0){bot[k] = k;return;}

	dfs2(son[k],tp);bot[k] = bot[son[k]];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

typedef long long ll;

ll val[MAXN];

ll f[MAXN][2],g[MAXN][2];

bool vis[MAXN];

void dp(int k)

{

	vis[k] = true;

	f[k][0] = g[k][0] = 0;

	f[k][1] = g[k][1] = val[k];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dp(e[i].to);

		f[k][0] += f[e[i].to][1];

		f[k][1] += min(f[e[i].to][1],f[e[i].to][0]);

		if(e[i].to == son[k])continue;

		g[k][0] += f[e[i].to][1];

		g[k][1] += min(f[e[i].to][1],f[e[i].to][0]);

	}

	return;

}

struct matrix

{

	ll m[2][2];

	matrix(){memset(m,0x3f,sizeof(m));}

	friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

		for(int i = 0;i <= 1;++i)

			for(int j = 0;j <= 1;++j)

				for(int k = 0;k <= 1;++k)

					c.m[i][j] = min(c.m[i][j],a.m[i][k] + b.m[k][j]);

		return c;

	}

	ll calc()

	{

		return min(min(m[0][0],m[0][1]),min(m[1][0],m[1][1]));

	}

};

struct node

{

	int lc,rc;

	matrix s;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

#define INF 10000000001

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)

	{

		t[rt].s.m[0][0] = INF;

		t[rt].s.m[0][1] = g[th[l]][0];

		t[rt].s.m[1][0] = t[rt].s.m[1][1] = g[th[l]][1];

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	t[rt].s = t[t[rt].lc].s * t[t[rt].rc].s;

	return;

}

void maintain(int rt,int p,int l,int r)

{

	if(l == r)

	{

		t[rt].s.m[0][0] = INF;

		t[rt].s.m[0][1] = g[th[l]][0];

		t[rt].s.m[1][0] = t[rt].s.m[1][1] = g[th[l]][1];

		return;

	}

	if(p <= mid)maintain(t[rt].lc,p,l,mid);

	else maintain(t[rt].rc,p,mid + 1,r);

	t[rt].s = t[t[rt].lc].s * t[t[rt].rc].s;

	return;

}

matrix query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].s;

	if(R <= mid)return query(t[rt].lc,L,R,l,mid);

	if(L > mid)return query(t[rt].rc,L,R,mid + 1,r);

	return query(t[rt].lc,L,R,l,mid) * query(t[rt].rc,L,R,mid + 1,r);

}

void modify(int k,ll v)

{

	g[k][1] += v - val[k];

	val[k] = v;

	while(k != 0)

	{

		matrix a = query(root,rnk[top[k]],rnk[bot[k]],1,n);

		maintain(root,rnk[k],1,n);

		matrix b = query(root,rnk[top[k]],rnk[bot[k]],1,n);

		int anc = fa[top[k]];

		g[anc][0] += min(b.m[1][0],b.m[1][1]) - min(a.m[1][0],a.m[1][1]);

		g[anc][1] += b.calc() - a.calc();

		k = anc;

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	char c[10];scanf("%s",c);

	for(int i = 1;i <= n;++i)scanf("%d",&val[i]);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dfs1(1,1);dfs2(1,1);

	dp(1);

	build(root,1,n);

	int x,y;

	ll v1,v2;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d%d",&x,&a,&y,&b);

		v1 = val[x];v2 = val[y];

		if(a == 1)modify(x,-INF);

		else modify(x,INF);

		if(b == 1)modify(y,-INF);

		else modify(y,INF);

		matrix res = query(root,rnk[top[1]],rnk[bot[1]],1,n);

		ll ans = min(min(res.m[0][0],res.m[0][1]),min(res.m[1][0],res.m[1][1]));

		if(a == 1)ans += INF + v1;

		if(b == 1)ans += INF + v2;

		if(ans >= INF - 100)ans = -1;

		printf("%lld\n",ans);

		modify(x,v1);modify(y,v2);

	}

	return 0;

}

Solution2：

注意每次会发生情况的点只有两个，因此完全不需要动态 $DP$ 这种东西，我们可以预处理一个 $f[i][0/1]$ 表示整棵子树的答案，其中根节点选或不选，再预处理一个 $g[i][0/1]$ 表示除去这棵子树之外的答案，这个可以换根 $DP$ 求，然后再预处理一个 $dp[k][i][0/1][0/1]$ 表示从 $k$ 开始往上跳 $2^j$ 步，这个点选没选，上面那个点选没选，这一条链上不算起始点伸出去的子树的 $DP$ 值，然后每次在找 $LCA$ 的时候顺便统计答案就行了，注意在 $LCA$ 那里有一些细节。

Code2：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

    register int res = 0,f = 1;register char c = getchar();

    while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

    while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

    return res * f;

}

int n,m;

#define MAXN 100010

int val[MAXN];

struct edge{int to,nxt;}e[MAXN << 1];

int edgenum = 0,lin[MAXN] = {0};

void add(int a,int b)

{

    e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

    e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

    return;

}

int fa[MAXN][18];

typedef long long ll;

ll f[MAXN][2],g[MAXN][2];

ll dp[MAXN][18][2][2];

int dep[MAXN];

void dp1(int k)

{

    dep[k] = dep[fa[k][0]] + 1;

    f[k][1] = val[k];

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to == fa[k][0])continue;

        fa[e[i].to][0] = k;

        dp1(e[i].to);

        f[k][0] += f[e[i].to][1];

        f[k][1] += min(f[e[i].to][1],f[e[i].to][0]); 

    }

    return;

}

void dp2(int k)

{

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to == fa[k][0])continue;

        g[e[i].to][0] = g[k][1] + f[k][1] - min(f[e[i].to][1],f[e[i].to][0]);

        g[e[i].to][1] = min(g[e[i].to][0],g[k][0] + f[k][0] - f[e[i].to][1]); 

        dp2(e[i].to);

    }

    return;

}

ll dpa[19][2],dpb[19][2];

ll query(int a,int x,int b,int y)

{

    if(dep[a] < dep[b])swap(a,b),swap(x,y);

    ll ans = f[a][x];

    dpa[18][x] = 0;dpa[18][x ^ 1] = 10000000000;

    for(int i = 17;i >= 0;--i)

    {

        if(dep[fa[a][i]] >= dep[b])

        {

            dpa[i][0] = min(dpa[i + 1][0] + dp[a][i][0][0],dpa[i + 1][1] + dp[a][i][1][0]);

            dpa[i][1] = min(dpa[i + 1][0] + dp[a][i][0][1],dpa[i + 1][1] + dp[a][i][1][1]);

            a = fa[a][i];

        }

        else

        {

            dpa[i][0] = dpa[i + 1][0];dpa[i][1] = dpa[i + 1][1];

        }

    }

    if(a == b)return ans + dpa[0][y] + g[b][y];

    ans += f[b][y];

    dpb[18][y] = 0;dpb[18][y ^ 1] = 10000000000;

    dpa[18][0] = dpa[0][0];dpa[18][1] = dpa[0][1];

    for(int i = 17;i >= 0;--i)

    {

        if(fa[a][i] != fa[b][i])

        {

            dpa[i][0] = min(dpa[i + 1][0] + dp[a][i][0][0],dpa[i + 1][1] + dp[a][i][1][0]);

            dpa[i][1] = min(dpa[i + 1][0] + dp[a][i][0][1],dpa[i + 1][1] + dp[a][i][1][1]);

            a = fa[a][i];

            dpb[i][0] = min(dpb[i + 1][0] + dp[b][i][0][0],dpb[i + 1][1] + dp[b][i][1][0]);

            dpb[i][1] = min(dpb[i + 1][0] + dp[b][i][0][1],dpb[i + 1][1] + dp[b][i][1][1]);

            b = fa[b][i];

        }

        else

        {

            dpa[i][0] = dpa[i + 1][0];dpa[i][1] = dpa[i + 1][1];

            dpb[i][0] = dpb[i + 1][0];dpb[i][1] = dpb[i + 1][1];

        }

    }

    int v = fa[a][0];

    ll val0 = g[v][0] + f[v][0] - f[a][1] - f[b][1];

    ll val1 = g[v][1] + f[v][1] - min(f[a][0],f[a][1]) - min(f[b][0],f[b][1]);

    ll ans0 = min(val0,val1) + dpa[0][1] + dpb[0][1];

    ll ans1 = val1 + min(dpa[0][0],dpa[0][1]) + min(dpb[0][0],dpb[0][1]);

    return ans + min(ans0,ans1);

}

int main()

{

    char c[3];

    scanf("%d%d%s",&n,&m,c);

    for(int i = 1;i <= n;++i)val[i] = rd();

    int a,b;

    for(int i = 1;i < n;++i)

    {

        scanf("%d%d",&a,&b);

        add(a,b);

    }

    dp1(1);dp2(1);

    for(int i = 2;i <= n;++i)

    {

        dp[i][0][0][1] = f[fa[i][0]][1] - min(f[i][0],f[i][1]);

        dp[i][0][1][0] = f[fa[i][0]][0] - f[i][1];

        dp[i][0][1][1] = f[fa[i][0]][1] - min(f[i][0],f[i][1]);

        dp[i][0][0][0] = 10000000000;

    }

    for(int k = 1;k <= 17;++k)for(int i = 1;i <= n;++i)

    {

        fa[i][k] = fa[fa[i][k - 1]][k - 1];

        int v = fa[i][k - 1];

        dp[i][k][0][0] = min(dp[i][k - 1][0][0] + dp[v][k - 1][0][0],dp[i][k - 1][0][1] + dp[v][k - 1][1][0]);

        dp[i][k][0][1] = min(dp[i][k - 1][0][0] + dp[v][k - 1][0][1],dp[i][k - 1][0][1] + dp[v][k - 1][1][1]);

        dp[i][k][1][0] = min(dp[i][k - 1][1][0] + dp[v][k - 1][0][0],dp[i][k - 1][1][1] + dp[v][k - 1][1][0]);

        dp[i][k][1][1] = min(dp[i][k - 1][1][0] + dp[v][k - 1][0][1],dp[i][k - 1][1][1] + dp[v][k - 1][1][1]);

    }

    int x,y;

    for(int i = 1;i <= m;++i)

    {

        scanf("%d%d%d%d",&a,&x,&b,&y);

        ll res = query(a,x,b,y);

        if(res >= 10000000000)res = -1;

        printf("%lld\n",res);

    }

    return 0;

}