[题解][树剖优化dp] Gym - 103119I Nim Cheater [2020 ICPC Macau]

题目大意

对于当前集合中的元素，询问最少需要删掉价值和为多少的元素，才能使得剩下的元素异或和为0。（原题是nim取石子的典型博弈问题，这里已经简化了一层）

对于集合有两种操作：（每次操作之后输出一次查询结果）

1. ADD a b: 加入一个数值为a，权值为b的元素。
2. DEL: 删除最近一次ADD操作

空间限制：8M

思路

先不考虑空间限制的问题——那就是个典型的背包变形

f[i][j]表示前i个元素中选若干个数异或和为j的最大权值和（这样总权值和减去这个值就是需要扔掉的数的最小的权值和，这样设计状态在边界处理、转移等方面都会容易一些）

考虑第i个元素选还是不选： f[i][j] = min(f[i-1][j], f[i-1][j^a[i]] + b[i])

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> edge[40010];
int ask[40010];
int fa[40010];
int siz[40010], heavy[40010];
int f[32][16390];
int dp[16390];
int  a[40010], b[40010];
int ans[40010];
void dfs(int x)
{
    siz[x] = 1;
    for (int i = 0; i < edge[x].size(); i++)
    {
        int y = edge[x][i];
        dfs(y);
        if (siz[y] > siz[heavy[x]]) heavy[x] = y;
        siz[x] += siz[y];
    }
}

void calc(int x,int num, int sum)
{
    //cout <<endl<<endl<< x <<' '<<a[x]<<' '<<b[x]<<' '<<sum << endl;

    memcpy(dp, f[num], sizeof(dp));
    //for (int i = 0; i < 10; i++)  cout <<dp[i] <<' ';
    for (int i = 0; i < 16384; i++)
    {
        dp[i]=max(dp[i], f[num][i^a[x]]+b[x]);
    }
    //cout <<endl;
   // for (int i = 0; i < 10; i++)  cout <<dp[i] <<' ';
    ans[x] = sum-dp[0];
    memcpy(f[num], dp, sizeof(dp));
    for (int i = 0; i < edge[x].size(); i++)
    {
        int y = edge[x][i];
        if (y != heavy[x])
        {
             memcpy(f[num+1], f[num], sizeof(dp));
             calc(y, num+1, sum+b[y]);
        }
    }
    if (heavy[x] != 0)
    {
        calc(heavy[x], num, sum+b[heavy[x]]);
    }


}
int main()
{
    scanf("%d", &n);
    int last = 0, root= 0;
    for (int i = 1; i <= n; i++)
    {
        char s[10];
        scanf(" %s", s);
        if (s[0] == 'A')
        {
            scanf("%d%d", &a[i], &b[i]);
            if(root == 0)
            {
                root = i;
                last= i;
            }
            else {
                edge[last].push_back(i);
                fa[i] = last;
                last = i;
            }
            ask[i] = i;
        }
        else {
            last = fa[last];
            ask[i] = last;
        }

    }
    dfs(root);
    memset(f, -0x3f, sizeof(f));
    f[0][0] = 0;
    calc(root, 0, b[root]);
    for (int i = 1; i <= n; i++)
    {
        printf("%d\n", ans[ask[i]]);
    }

    return 0;
}
/*
7
ADD 3 10
ADD 2 4
ADD 1 5
ADD 2 1
DEL
DEL
ADD 3 5
*/