zcmimi's blog
avatar
zc
2020-10-21 16:41:02
  • 本文总阅读量

查看原题

点击跳转

解法一

最小权覆盖集 = 全集 - 最大权独立集

动态dp

只要把强制取点,不取点可以分别把点的权值改为正无穷与负无穷

解法二

倍增/树链剖分+树形dp

每次修改的两个点a,b构成一条链

可以链上连接的子树与链中间的点的结果不受修改影响,只有a,b的转移受影响,需要单独处理

那么我们可以把子树的答案都预处理出来,链中间部分可以用倍增或树链剖分维护

这样只需要处理a,b

#include<bits/stdc++.h>
const int N=100011;
int n,m,cnt,head[N],f[N][2],fa[N],d[N];
struct edge{int to,nxt;}e[N];
void add(int x,int y){e[++cnt].to=y,e[cnt].nxt=head[x],head[x]=cnt;}
#define fl(i,x) for(int i=head[x],to;i=e[i].to,i;i=e[i].nxt)
int max(int x,int y){return x>y?x:y;}
void dfs(int x){
    f[x][1]=1;
    fl(i,x)if(to!=fa[x])
        d[to]=d[x]+1,fa[to]=x,dfs(to),
        f[x][0]+=max(f[to][0],f[to][1]),
        f[x][1]+=f[to][0];
}
int main(){
    int a,x,b,y;char typ[5];
    scanf("%d%d%s",&n,&m,typ);
    for(int i=1;i<=n-1;++i)
        scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(1);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d%d",&a,&x,&b,&y);

    }
}
LG 5024 保卫王国
comment评论
Search
search