【NOIP2018】保卫王国

红太狼 2023-06-05 08:53 16阅读 0赞

### Description ###

给定一棵树，求它的最小点权覆盖集，其中允许强制某个点选或不选

### Solution ###

ddp用LCT维护

明确一个关系式：**最小点权覆盖集=全集-最大点权独立集**

那么n≤2000的暴力就很简单了，暴力修改，然后求最大点权独立集就好了（我在考场上就是这么写的）

关于正解，我采用的是动态dp（动态dp的题解[点这里][Link 1]）

根据上面的式子，我们用动态dp维护最大点权独立集，然后用全集减去就好了

然后我们考虑强制选点的限制

如果强制一个点选，那么我们将这个点的点权加上负无穷

如果强制不选，那么我们将这个点的点权加上正无穷，然后全集加上正无穷就好了

记得每次操作后要还原现场

时间复杂度是$O(mlogn)$

### Code ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 using namespace std;
      3 typedef long long ll;
      4 const int N = 1e5 + 10;
      5 const ll INF = 1ll << 40;
      6 inline int read() {
      7     int ret = 0, op = 1;
      8     char c = getchar();
      9     while (!isdigit(c)) {
     10         if (c == '-') op = -1; 
     11         c = getchar();
     12     }
     13     while (isdigit(c)) {
     14         ret = (ret << 3) + (ret << 1) + c - '0';
     15         c = getchar();
     16     }
     17     return ret * op;
     18 }
     19 struct Edge {
     20     int nxt, to;
     21 } e[N << 1];
     22 int num, head[N];
     23 struct Matrix {
     24     ll m[2][2];
     25     Matrix() {
     26         m[0][0] = m[0][1] = m[1][0] = m[1][1] = -INF;
     27     }
     28     inline ll getans() {
     29         return max(m[0][0], m[1][0]);
     30     }
     31     inline void build(ll x, ll y) {
     32         m[0][0] = m[0][1] = x;
     33         m[1][0] = y; m[1][1] = -INF;
     34     }
     35     Matrix operator *(const Matrix &x) const {
     36         Matrix ret;
     37         for (register int i = 0; i < 2; ++i)
     38             for (register int j = 0; j < 2; ++j)
     39                 for (register int k = 0; k < 2; ++k)
     40                     ret.m[i][j] = max(ret.m[i][j], m[i][k] + x.m[k][j]);
     41         return ret;
     42     }
     43 };
     44 struct LCT {
     45     int fa, ch[2];
     46     ll f[2];
     47     Matrix x;
     48 } a[N];
     49 int n, m, val[N];
     50 ll sum;
     51 string s;
     52 inline void add(int from, int to) {
     53     e[++num].nxt = head[from];
     54     e[num].to = to;
     55     head[from] = num;
     56 }
     57 void dfs(int now, int fa) {
     58     a[now].f[1] = val[now];
     59     for (register int i = head[now]; i; i = e[i].nxt) {
     60         int to = e[i].to;
     61         if (to == fa) continue ;
     62         a[to].fa = now;
     63         dfs(to, now);
     64         a[now].f[0] += max(a[to].f[1], a[to].f[0]);
     65         a[now].f[1] += a[to].f[0];
     66     }
     67     a[now].x.build(a[now].f[0], a[now].f[1]);
     68 }
     69 inline void update(int now) {
     70     a[now].x.build(a[now].f[0], a[now].f[1]);
     71     if (a[now].ch[0]) a[now].x = a[a[now].ch[0]].x * a[now].x; 
     72     if (a[now].ch[1]) a[now].x = a[now].x * a[a[now].ch[1]].x;
     73 }    
     74 inline int isnroot(int now) {
     75     return a[a[now].fa].ch[0] == now || a[a[now].fa].ch[1] == now;
     76 }
     77 inline void rotate(int x) {
     78     int y = a[x].fa;
     79     int z = a[y].fa;
     80     int xson = a[y].ch[1] == x;
     81     int yson = a[z].ch[1] == y;
     82     int B = a[x].ch[xson ^ 1];
     83     if (isnroot(y)) a[z].ch[yson] = x;
     84     a[y].ch[xson] = B;
     85     a[x].ch[xson ^ 1] = y;
     86     if (B) a[B].fa = y;
     87     a[y].fa = x;
     88     a[x].fa = z;
     89     update(y); update(x); 
     90 }
     91 void splay(int x) {
     92     while (isnroot(x)) {
     93         int y = a[x].fa;
     94         int z = a[y].fa;
     95         if (isnroot(y)) 
     96             (a[y].ch[0] == x) ^ (a[z].ch[0] == y) ? rotate(x) : rotate(y);
     97         rotate(x); 
     98     }
     99     update(x);
    100 }
    101 void access(int x) {
    102     for (register int y = 0; x; y = x, x = a[x].fa) {
    103         splay(x);
    104         if (a[x].ch[1]) {
    105             a[x].f[0] += a[a[x].ch[1]].x.getans();
    106             a[x].f[1] += a[a[x].ch[1]].x.m[0][0];
    107         }
    108         if (y) {
    109             a[x].f[0] -= a[y].x.getans();
    110             a[x].f[1] -= a[y].x.m[0][0];            
    111         }
    112         a[x].ch[1] = y;
    113         update(x);
    114     }
    115 }
    116 void change(int x, ll y) {
    117     access(x); splay(x);
    118     a[x].f[1] += y;
    119     update(x);
    120 }
    121 void solve(int x, int op1, int y, int op2) {
    122     change(x, op1 ? -INF : INF);
    123     change(y, op2 ? -INF : INF);
    124     splay(1);
    125     sum += ((op1 ^ 1) + (op2 ^ 1)) * INF;
    126     ll ans = sum - a[1].x.getans();
    127     change(x, op1 ? INF : -INF);
    128     change(y, op2 ? INF : -INF);    
    129     sum -= ((op1 ^ 1) + (op2 ^ 1)) * INF;
    130     if (ans > INF) puts("-1");
    131     else printf("%lld\n", ans);
    132 }
    133 int main() {
    134     n = read(); m = read(); cin >> s;
    135     for (register int i = 1; i <= n; ++i) {
    136         val[i] = read();
    137         sum += val[i];
    138     }
    139     for (register int i = 1; i < n; ++i) {
    140         int x = read(), y = read();
    141         add(x, y); add(y, x);
    142     }
    143     dfs(1, 0);
    144     while (m--) {
    145         int x = read(), op1 = read(), y = read(), op2 = read();
    146         solve(x, op1, y, op2);
    147     }
    148     return 0;
    149 }

AC Code

转载于:https://www.cnblogs.com/shl-blog/p/11367936.html

[Link 1]: https://www.cnblogs.com/shl-blog/p/11365207.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/55b3735a8590484f9f7d06696ab87b70.png