模板题

动态修改节点权值求树上最大权点独立集。

首先考虑朴素dp：
设$f_{u,0/1}$表示节点$u$不选/选，$u$子树内最大权独立集的大小。
转移就是（$v$是$u$的所有儿子）：
{ f u , 0 = ∑ v max ⁡ { f v , 0 , f v , 1 } f u , 1 = h u + ∑ v f v , 0 \left\{\begin{matrix} f_{u,0}={\underset{v}\sum}\max\{f_{v,0},f_{v,1}\}\\ f_{u,1}=h_u+{\underset{v}\sum}f_{v,0}\hspace{0.95cm} \end{matrix}\right. ⎩ ⎨ ⎧​fu,0​=v∑​max{fv,0​,fv,1​}fu,1​=hu​+v∑​fv,0​​

考虑到修改影响的节点是从节点$u$到根节点$1$的一条路径。

如果每次修改都暴力重新dp一下路径上的点理论上过不去。

考虑到一条到根的路径上只有$O(\log n)$条重链，换句话说路径上只有$O(\log n)$个节点是其父亲的轻儿子。

我们考虑树剖维护重儿子到父亲的转移，暴力轻儿子到父亲的转移。

首先是先对轻重儿子分治，老套路了：

设$g_{u,0/1}$表示$u$节点不选/选，只考虑$u$的轻儿子所在的子树（假设重儿子所在子树不存在），最大权独立集的大小。

记$so{n}_u$表示$u$的重儿子，转移就是：
{ g u , 0 = ∑ v ≠ s o n u max ⁡ { f v , 0 , f v , 1 } g u , 1 = h u + ∑ v ≠ s o n u f v , 0 \left\{\begin{matrix} g_{u,0}={\underset{v\not= son_u}\sum}\max\{f_{v,0},f_{v,1}\} \\ g_{u,1}=h_u+{\underset{v\not= son_u}\sum}f_{v,0}\hspace{0.9cm} \end{matrix}\right. ⎩ ⎨ ⎧​gu,0​=v=sonu​∑​max{fv,0​,fv,1​}gu,1​=hu​+v=sonu​∑​fv,0​​

同时，用$g$可以还原出$f$：
{ f u , 0 = g u , 0 + m a x { f s o n u , 0 , f s o n u , 1 } f u , 1 = g u , 1 + f s o n u , 0 \left\{\begin{matrix} f_{u,0}=g_{u,0}+max\left\{f_{son_u,0},f_{son_u,1}\right\}\\ f_{u,1}=g_{u,1}+f_{son_u,0}\hspace{2.24cm} \end{matrix}\right. {fu,0​=gu,0​+max{fsonu​,0​,fsonu​,1​}fu,1​=gu,1​+fsonu​,0​​

我们考虑如何快速修改重儿子。

把转移方程写成Floyd矩乘的形式：

定义矩阵广义矩阵乘法为：
$A_{n,m}\ast B_{m,p}=C_{n,p}$
$c_{i,j}=\stackrel{m}{\underset{k=0}{⨁}}{a}_{i,k}\otimes b_{k,j}$

在本题中$\oplus$为$\max$运算，$\otimes$为$+$运算，也就是$\max ,+$矩乘：
c i , j = max ⁡ k = 0 m { a i , k + b k , j } c_{i,j}=\overset{m}{\underset{k=0}{\max }}\left\{a_{i,k}+ b_{k,j}\right\} ci,j​=k=0max​m​{ai,k​+bk,j​}

我们要用线段树维护重链，因此要考虑如何用$f_{so{n}_u}$推出$f_u$。

写成矩阵乘法就是：
$X\ast \left[\begin{array}{c}{f}_{so{n}_u,0}\\ f_{so{n}_u,1}\end{array}\right]=\left[\begin{array}{c}{f}_{u,0}\\ f_{u,1}\end{array}\right]$

这里用左乘系数矩阵，参照普通矩阵乘法的证明，显然这个矩阵乘法也符合结合律。

现在看看$X$填什么。

首先知道：
f u , 0 = g u , 0 + max ⁡ { f s o n u , 0 , f s o n u , 1 } f_{u,0}=g_{u,0}+\max\left\{f_{son_u,0},f_{son_u,1}\right\} fu,0​=gu,0​+max{fsonu​,0​,fsonu​,1​}
把它搞成矩阵乘法的形式：
f u , 0 = max ⁡ { g u , 0 + f s o n u , 0 , g u , 0 + f s o n u , 1 } f_{u,0}=\max\left\{g_{u,0}+f_{son_u,0},g_{u,0}+f_{son_u,1}\right\} fu,0​=max{gu,0​+fsonu​,0​,gu,0​+fsonu​,1​}

同理：
$f_{u,1}=g_{u,1}+f_{so{n}_u,0}$

变成：
f u , 1 = max ⁡ { g u , 1 + f s o n u , 0 , − ∞ + f s o n u , 1 } f_{u,1}=\max\left\{g_{u,1}+f_{son_u,0},-\infty+f_{son_u,1}\right\} fu,1​=max{gu,1​+fsonu​,0​,−∞+fsonu​,1​}

因此：
$\left[\begin{array}{cc}{g}_{u,0}& g_{u,0}\\ g_{u,1}& -\infty \end{array}\right]\left[\begin{array}{c}{f}_{so{n}_u,0}\\ f_{so{n}_u,1}\end{array}\right]=\left[\begin{array}{c}{f}_{u,0}\\ f_{u,1}\end{array}\right]$

那我们就可以先树剖一下，然后用线段树维护矩阵连乘积。
每次修改的时候，我们可以暴力修改$x$位置的$g$矩阵，进而得到$x$所在重链链顶的新的$f$矩阵，来更新$x$链顶的父亲的$g$矩阵，然后不断重复这个过程直到递归到根节点所在重链。（根节点所在重链的链顶没有父亲）

话说这个矩阵乘法的单位矩阵是什么？
回想一下经典矩阵乘法（$+,\times$矩乘）的单位矩阵：
[ 1 0 0 0 1 0 0 0 1 ] \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} ​100​010​001​ ​

我们会发现，$1$是$\times$的单位元，$0$是$+,\times$的零元。

对于$\max ,+$矩乘：
我们会发现：$0$是$+$的单位元，$-\infty$是$\max ,+$的零元。
因此单位矩阵就是：
[ 0 − ∞ − ∞ − ∞ 0 − ∞ − ∞ − ∞ 0 ] \begin{bmatrix} 0 & -\infty & -\infty \\ -\infty & 0 & -\infty \\ -\infty & -\infty & 0 \end{bmatrix} ​0−∞−∞​−∞0−∞​−∞−∞0​ ​

当然这道题只有2阶矩阵，因此单位矩阵其实是：

$\left[\begin{array}{cc}0& -\infty \\ -\infty & 0\end{array}\right]$

还是说一说代码：

int main() {
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++) cin>>h[i];
	a.resize(n+1);
	for(int i=1,u,v; i<n; i++) {
		cin>>u>>v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	dfs1(1);
	dfs2(1,1);前两遍dfs是树剖
	dfs3(1);求出初始的f和g
	build(1,1,n);初始化线段树
//	for(int i=1;i<=n;i++) 
//		cout<<i<<':'<<f[i][0]<<' '<<f[i][1]<<' '<<g[i][0]<<' '<<g[i][1]<<endl;
	for(int i=1;i<=n;i++) 
		push(1,dfn[i],dfn[i],{g[i][0],g[i][0],g[i][1],int(-1e9)});用一开始的g来建立线段树
	while(m--) {
		int u,x;
		cin>>u>>x;
		mat val=find(1,dfn[u],dfn[u]);获得u现在的矩阵
		val[1][0]-=h[u]-x;	撤销原来的h[u]，把原来h[u]的位置变为x，修改矩阵
		h[u]=x;				更新h[u]，以便下次修改矩阵
		pushx(u,val);		把新的u的矩阵放进去
		cout<<max(F(1)[0][0],F(1)[1][0])<<endl;
	}
}

然后主要是如何更新：

mat F(int u) {
	用F(i)表示i的f矩阵，其实是一个列向量，但是为了方便，我们把列向量右边增加一列，扩展为2*2的矩阵。
	因此F(i)只有第一列的两个数字是有意义的。
	return find(1,dfn[u],dfn[bot[u]])*mat{0,int(-1e9),0,int(-1e9)};
	查询一个位置的F需要求出从它开始到它所在重链底端的矩阵连乘积，再右乘上重链底部节点的F矩阵
	但是重链底部节点一定是叶子，所以它的F矩阵一定是一个长度为2的全零列向量，把它扩展为一个二阶方阵。
	其实右边两个数填啥都行，这里习惯填为-1e9
}			
void pushx(int u,const mat&val) {
	函数pushx(u,val)表示把节点u的矩阵修改为val，同时递归修改上级重链的F值
	
	mat ago=F(top[u]);提前记录一下以前的链顶F值，方便修改
	push(1,dfn[u],dfn[u],val);
	if(!fa[top[u]]) return ;如果说链顶没有父亲，就结束
	
	否则还需要更新链顶父亲的g矩阵
	mat now=F(top[u]);获得链顶现有的f值
	mat x=find(1,dfn[fa[top[u]]],dfn[fa[top[u]]]);获得链顶父亲的g矩阵
	
	接下来三行去除原来的f[top[u]]的贡献，加上新的贡献：
	x[0][0]=x[0][0]-max(ago[0][0],ago[1][0])+max(now[0][0],now[1][0]);
	x[0][1]=x[0][0];
	x[1][0]=x[1][0]-ago[0][0]+now[0][0];
	pushx(fa[top[u]],x)递归调用函数修改链顶的父亲;
}

还有一个小细节就是，矩阵乘法没有交换律，因此在push_up的时候以及计算贡献的时候需要注意乘法的方向。
左乘系数矩阵就是先乘左边再乘右边。

完整代码：

#include<iostream>
#include<vector>
using namespace std;
const int N=1e5;
vector<vector<int>> a;
int dep[N+5],siz[N+5],top[N+5],bot[N+5],son[N+5],dfn[N+5],fa[N+5],tot;
int dfs1(int u) {
	siz[u]=1;
	dep[u]=dep[fa[u]]+1;
	for(auto&v:a[u])
		if(v^fa[u]) {
			fa[v]=u;
			siz[u]+=dfs1(v);
			if(siz[son[u]]<siz[v]) son[u]=v;
		}
	return siz[u];
}
int dfs2(int u,int t) {
	dfn[u]=++tot;
	top[u]=t;
	bot[u]=son[u]?dfs2(son[u],t):u;
	for(auto&v:a[u])
		if(v^fa[u]&&v^son[u])
			dfs2(v,v);
	return bot[u];
}
int h[N+5];
class mat {
	public:
		int a[2][2];
		mat() {
			a[0][0]=a[1][1]=0;
			a[0][1]=a[1][0]=-1e9;
		}
		int*operator[](int x) {
			return a[x];
		}
		mat(int x,int y,int z,int w) {
			a[0][0]=x;
			a[0][1]=y;
			a[1][0]=z;
			a[1][1]=w;
		}
		mat(const mat&x) {
			for(int i=0; i<2; i++) for(int j=0; j<2; j++) a[i][j]=x.a[i][j];
		}
		mat&operator=(const mat& x) {
			for(int i=0; i<2; i++) for(int j=0; j<2; j++) a[i][j]=x.a[i][j];
			return *this;
		}
		friend mat operator*(const mat&,const mat&);
};
mat operator*(const mat&a,const mat&b) {
	mat c={(int)-1e9,(int)-1e9,(int)-1e9,(int)-1e9};注意初值设置
//	mat c;
	for(int i=0; i<2; i++) 
		for(int j=0; j<2; j++) 
			for(int k=0;k<2;k++) 
				c[i][j]=max(c[i][j],a.a[i][k]+b.a[k][j]);
	return c;
}
struct node {
	int l,r;
	mat val;
} t[N<<2];
void build(int u,int l,int r) {
	t[u]= {l,r};
	if(l==r) return;
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
}
void push_up(int u) {
	t[u].val=t[u<<1].val*t[u<<1|1].val;
}
void push_down(int u) {

}
void push(int u,int l,int r,const mat& val) {
	if(l<=t[u].l&&t[u].r<=r) t[u].val=val;
	else {
		int mid=t[u].l+t[u].r>>1;
		if(l<=mid) push(u<<1,l,r,val);
		if(mid<r) push(u<<1|1,l,r,val);
		push_up(u);
	}
}
mat find(int u,int l,int r) {
	if(l<=t[u].l&&t[u].r<=r) return t[u].val;
	int mid=t[u].l+t[u].r>>1;
	mat ans;
	if(l<=mid) ans=ans*find(u<<1,l,r);
	if(mid<r) ans=ans*find(u<<1|1,l,r);
	return ans;
}
int f[N+5][2],g[N+5][2];
void dfs3(int u) {
	g[u][1]=h[u];
	for(auto&v:a[u]) 
		if(v^fa[u]) {
			dfs3(v);
			if(son[u]^v) g[u][0]+=max(f[v][0],f[v][1]),g[u][1]+=f[v][0];
		}
	f[u][0]=g[u][0]+max(f[son[u]][0],f[son[u]][1]);
	f[u][1]=g[u][1]+f[son[u]][0];
}
mat F(int u) {
	return find(1,dfn[u],dfn[bot[u]])*mat{0,int(-1e9),0,int(-1e9)};
}
void pushx(int u,const mat&val) {
	mat ago=F(top[u]);
	push(1,dfn[u],dfn[u],val);
	if(!fa[top[u]]) return ;
	mat now=F(top[u]);
	mat x=find(1,dfn[fa[top[u]]],dfn[fa[top[u]]]);
	x[0][0]=x[0][0]-max(ago[0][0],ago[1][0])+max(now[0][0],now[1][0]);
	x[0][1]=x[0][0];
	x[1][0]=x[1][0]-ago[0][0]+now[0][0];
	pushx(fa[top[u]],x);
}
int main() {
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++) cin>>h[i];
	a.resize(n+1);
	for(int i=1,u,v; i<n; i++) {
		cin>>u>>v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	dfs1(1);
	dfs2(1,1);
	dfs3(1);
	build(1,1,n);
//	for(int i=1;i<=n;i++) 
//		cout<<i<<':'<<f[i][0]<<' '<<f[i][1]<<' '<<g[i][0]<<' '<<g[i][1]<<endl;
	for(int i=1;i<=n;i++) 
		push(1,dfn[i],dfn[i],{g[i][0],g[i][0],g[i][1],int(-1e9)});
	while(m--) {
		int u,x;
		cin>>u>>x;
		mat val=find(1,dfn[u],dfn[u]);
		val[1][0]-=h[u]-x;
		h[u]=x;
		pushx(u,val);
		cout<<max(F(1)[0][0],F(1)[1][0])<<endl;
	}
}
/*
几组hack:

3 10000
1 2 4
1 2
1 3
1 1000

3 10000
1 2 4
1 2
1 3
3 0

5 10000
1 2 4 8 16
1 2
1 5
2 3 
2 4

*/

模板题2

动态修改节点权值求树上最小权点覆盖集

因为如果选的话就相当于强制不选的费用为$+\infty$，不选就相当于强制选的费用为$+\infty$。
这挺好理解的。
怎么强制不选的费用呢？可以理解为给这个节点下面连一个权值为$+\infty$的儿子。
当然实现不需要这么麻烦。

设$f_{u,0/1}$表示节点$u$不选/选的贡献，则：
{ f u , 0 = ∑ v f v , 1 f u , 1 = h u + ∑ v min ⁡ { f v , 0 , f v , 1 } \left\{\begin{matrix} f_{u,0}=\underset{v}{\sum}f_{v,1}\hspace{2.5cm}\\ f_{u,1}=h_u+\underset{v}{\sum}\min \{f_{v,0},f_{v,1}\} \end{matrix}\right. ⎩ ⎨ ⎧​fu,0​=v∑​fv,1​fu,1​=hu​+v∑​min{fv,0​,fv,1​}​

同理对轻重儿子分治，设$g_u$表示只考虑轻儿子的子树，节点$u$不选/选的的贡献：
{ g u , 0 = ∑ v ≠ s o n u f v , 1 g u , 1 = h u + ∑ v ≠ s o n u min ⁡ { f v , 0 , f v , 1 } \left\{\begin{matrix} g_{u,0}=\underset{v\not =son_u}{\sum}f_{v,1}\hspace{2.6cm}\\ g_{u,1}=h_u+\underset{v\not=son_u}{\sum}\min \{f_{v,0},f_{v,1}\} \end{matrix}\right. ⎩ ⎨ ⎧​gu,0​=v=sonu​∑​fv,1​gu,1​=hu​+v=sonu​∑​min{fv,0​,fv,1​}​

然后写出从$g$到$f$的转移：

{ f u , 0 = g u , 0 + f s o n u , 1 f u , 1 = g u , 1 + min ⁡ { f s o n u , 0 , f s o n u , 1 } \left\{\begin{matrix} f_{u,0}=g_{u,0}+f_{son_u,1}\hspace{2.1cm}\\ f_{u,1}=g_{u,1}+\min\{f_{son_u,0},f_{son_u,1}\}\end{matrix}\right. {fu,0​=gu,0​+fsonu​,1​fu,1​=gu,1​+min{fsonu​,0​,fsonu​,1​}​

最后写出$+,\min$矩乘的转移：
$\left[\begin{array}{cc}+\infty & g_{u,0}\\ g_{u,1}& g_{u,1}\end{array}\right]\left[\begin{array}{c}{f}_{so{n}_u,0}\\ f_{so{n}_u,1}\end{array}\right]=\left[\begin{array}{c}{f}_{u,0}\\ f_{u,1}\end{array}\right]$

于是可以树剖来维护。

注意把输出-1的情况给判掉就可以了。显然只有直接父子之间都不能选时才输出-1。

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
const int N=1e5;
vector<vector<int>> a;
long long b[N+5];
int dep[N+5],siz[N+5],top[N+5],dfn[N+5],fa[N+5],bot[N+5],son[N+5],tot;
int dfs1(int u) {
	dep[u]=dep[fa[u]]+1;
	siz[u]=1;
	for(auto&v:a[u])
		if(v^fa[u]) {
			fa[v]=u;
			siz[u]+=dfs1(v);
			if(siz[son[u]]<siz[v]) son[u]=v;
		}
	return siz[u];
}
int dfs2(int u,int t) {
	dfn[u]=++tot;
	top[u]=t;
	bot[u]=son[u]?dfs2(son[u],t):u;
	for(auto&v:a[u])
		if(v^fa[u]&&v^son[u])
			dfs2(v,v);
	return bot[u];
}
class mat {
	public:
		long long a[2][2];
		mat() {
			a[0][0]=a[1][1]=0,a[1][0]=a[0][1]=1e18;
		}
		mat(long long x,long long y,long long z,long long w) {
			a[0][0]=x;
			a[0][1]=y;
			a[1][0]=z;
			a[1][1]=w;
		}
		long long*operator[](int x) {
			return a[x];
		}
		mat(const mat&b) {
			for(int i=0; i<2; i++)
				for(int j=0; j<2; j++)
					a[i][j]=b.a[i][j];
		}
		mat operator=(const mat &b) {
			for(int i=0; i<2; i++)
				for(int j=0; j<2; j++)
					a[i][j]=b.a[i][j];
			return *this;
		}
		mat operator*(mat b) {
			mat c= {(long long)1e16,(long long)1e16,(long long)1e16,(long long)1e16};
			for(int i=0; i<2; i++)
				for(int j=0; j<2; j++)
					for(int k=0; k<2; k++)
						c[i][j]=min(c[i][j],a[i][k]+b[k][j]);
			return c;
		}
};
struct node {
	int l,r;
	mat val;
} t[N<<2];
void build(int u,int l,int r) {
	t[u]= {l,r};
	if(l==r) return;
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
}
void push_up(int u) {
	t[u].val=t[u<<1].val*t[u<<1|1].val;
}
void push(int u,int l,int r,mat& val) {
	if(l<=t[u].l&&t[u].r<=r) t[u].val=val;
	else {
		int mid=t[u].l+t[u].r>>1;
		if(l<=mid) push(u<<1,l,r,val);
		if(mid<r) push(u<<1|1,l,r,val);
		push_up(u);
	}
}
mat find(int u,int l,int r) {
	if(l<=t[u].l&&t[u].r<=r) return t[u].val;
	int mid=t[u].l+t[u].r>>1;
	mat ans;
	if(l<=mid) ans=ans*find(u<<1,l,r);
	if(mid<r) ans=ans*find(u<<1|1,l,r);
	return ans;
}
long long f[N+5][2],g[N+5][2];
void dfs3(int u) {
	g[u][1]=b[u];
	for(auto&v:a[u])
		if(v^fa[u]) {
			dfs3(v);
			if(v^son[u])
				g[u][0]+=f[v][1],
				         g[u][1]+=min(f[v][0],f[v][1]);
		}
	f[u][0]=g[u][0]+f[son[u]][1];
	f[u][1]=g[u][1]+min(f[son[u]][0],f[son[u]][1]);
}
mat F(int x) {
	return find(1,dfn[x],dfn[bot[x]])*mat {0,(long long)1e16,(long long)0,(long long)1e16};
}
void pushx(int u,mat&val) {
	mat ago=F(top[u]);
	push(1,dfn[u],dfn[u],val);
	mat now=F(top[u]);
	if(!fa[top[u]]) return;
	mat x=find(1,dfn[fa[top[u]]],dfn[fa[top[u]]]);
	x[0][1]=x[0][1]-ago[1][0]+now[1][0];
	x[1][0]=x[1][0]-min(ago[0][0],ago[1][0])+min(now[0][0],now[1][0]);
	x[1][1]=x[1][0];
	pushx(fa[top[u]],x);
}
//void print(int u) {
//	printf("%d:[%d,%d]:\n%lld %lld\n%lld %lld\n\n",u,t[u].l,t[u].r,t[u].val[0][0],t[u].val[0][1],t[u].val[1][0],t[u].val[1][1]);
//}
//void check(int u) {
//	print(u);
//	if(t[u].l==t[u].r) return ;
//	check(u<<1);
//	check(u<<1|1);
//}
int main() {
	int n,m;
	string s;
	cin>>n>>m>>s;
	a.resize(n+1);
	for(int i=1; i<=n; i++) cin>>b[i];
	for(int i=1,u,v; i<n; i++) {
		cin>>u>>v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	dfs1(1);
	dfs2(1,1);
	dfs3(1);
	build(1,1,n);
	for(int i=1; i<=n; i++) {
		mat t= {(long long)1e16,g[i][0],g[i][1],g[i][1]};
		push(1,dfn[i],dfn[i],t);
	}

	while(m--) {
		int x,y;
		bool p,q;
		cin>>x>>p>>y>>q;
		if(dep[x]>dep[y]) swap(x,y),swap(p,q);
		这是为了确保要么x是y的祖先，要么x,y不在一个子树上。
		因为我们修改两个节点时使用了取巧的方法。
		我们加入的时候记录一下原来x的矩阵和原来y的矩阵，然后算出修改的矩阵。
		然后我们先把x的新矩阵加入，再把y的新矩阵加入。
		删除的时候先把y原来的加入，再把x原来的矩阵加入。

		因为修改子孙可能会对祖先的矩阵产生影响。
	假如我们先加入修改过后的y矩阵（yt），此时设受到影响的x矩阵变为t，再加入修改过后的x矩阵（xt）。
	但是xt是在xv的基础上计算出来的，不是在t的基础上计算出来的，就可能导致错误。
	
		if(!p&&!q&&(fa[x]==y||fa[y]==x)) {
			cout<<-1<<endl;
			continue;
		}
		mat xv=find(1,dfn[x],dfn[x]),yv=find(1,dfn[y],dfn[y]),
		    xt=p?mat {(long long)1e16,(long long)1e14,xv[1][0],xv[1][1]}
		       :
		       mat {(long long)1e16,xv[0][1],(long long)1e14,(long long)1e14},
		       yt=q?mat {(long long)1e16,(long long)1e14,yv[1][0],yv[1][1]}
		          :
		          mat {(long long)1e16,yv[0][1],(long long)1e14,(long long)1e14};
		pushx(x,xt);注意加入的顺序
		pushx(y,yt);

		mat ans=F(1);
		cout<<min(ans[0][0],ans[1][0])<<endl;
		pushx(y,yv);注意撤销的顺序
		pushx(x,xv);

	}
}
/*
3 10000 X
1 2 4
1 2
1 3


4 100000 X
1 2 4 8
1 2
1 3
2 4
1 1 3 1
1 1 4 1


*/

后记

最大权独立集+最小权覆盖集=全集。

于是皆大欢喜。