2022"杭电杯"中超联赛·第六场（06树形DP）

这一场打的很烂，队友一直在开计算几何没有做出来，而我也不会做，最近被好几场比赛压着了，所以我还是简短的写一下题吧，补题等到后面再说吧。

1006 Maex（树形DP）

题意：给你一个 $n$ 个点的树，求每一个结点包括其子树的 $MEX$ 值的和的最大值。

思路：对于一个子树来看，通过对于 $MEX$ 的理解，如果没有出现 $0$ 那么值一直为 $0$ ，所以我们想要填 $0$ 。那么填完之后应该填什么？应该填 $1$ ...我想要求出最大值，那么肯定是想要 $0$ 在最底下，然后让上面的都可以利用它，这样就是一个最长链了。那么就求深度然后得到最长链填 $0$ 吗，如果子树的其他支链有什么关系呢？我们来看下面这个图：

这张图可以对比两种：左边是最深链，右边是多链

我们对其分别进行计算，发现并不是最深链，还需要看其他支链。原因是我虽然链少，但是我可以通过其他子结点来堆，使得我的当前结点变高，例如这个四个父亲的结点 $6$ ，因为子结点很多，它的 $MEX$ 可以很大。

左边是最深链，右边是多链.很明显，不能只看最深链

所以我们需要维护两个值，一个是子结点个数，这样来看加上子结点个数就是自己的 $MEX$ 值，然后每次加上儿子结点的 $Max$ 值即可。

代码：

inline void dfs(int x,int pre)
{
    num[x] = 1;//首先肯定得有自己
    int res = 0;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y = edge[i].to;
        if (y==pre) continue;
        dfs(y,x);
        res = Max(res, f[y]);
        num[x] += num[y];//维护子结点个数
    }
    f[x] = res + num[x];//维护当前答案
}
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) head[i] = 0;
    cnt = 0;

    for (int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    cout<<f[1]<<endl;
}

1012 Loop（链表）

题意：给你一个长度为 $n$ 的序列，你可以进行 $k$ 次操作，选择一个数让其放到后面的任意位置（可以不动），求操作结束后的最大序列（字典序最大）。

思路：经过推断，可以先求出逆序对，例如 $[4,3,1,2]$ 那么说明如果有机会我们需要将 $1$ 放到 $2$ 的后面使其变成 $[4,3,2,1]$ 。这样就能保证字典序最大。

那么如果有多个逆序对怎么办呢？例如 $[4,5,1,2,7,6,5,7]$ ，图中有 $[1,2],[2,7],[5,7]$ 三对逆序对，我们需要交换最大的 $[5,7]$ 吗？不是，我们需要交换最前面的 $[1,2]$ ，因为字典序是从前往后的，所以前面的满足条件的话当然是最大的。

那么相当于我取出来两个数，接下来如何看？例如上面那个例子，我取出 $[1]$ 实际上现在应该看 $[4,5,2,7,6,5,7]$ 这个时候要比较 $2$ 两端的，所以我们需要用 $O(1)$ 的链表来做。

inline void remove(int cur)
{
    vis[cur] = 0;
    r[ l[cur] ]=r[cur];
    l[ r[cur] ]=l[cur];
    int x = l[cur], y = r[cur];
    if (a[x]<a[y]) q.push(x);//又产生逆序对
}

所以我们用一个优先队列来存放每次的最前面的，每次取出来的就是最前面的。

那么取出来的数放在哪呢？

放在最后第一个降序的地方，一次往前面插，对于当前的数，把大于它的插前面，这样保证字典序最大，例如现在变成 $[3,4,5,7,\underline{3},1]$ ，现在取出来了 $[4,3,2]$ 那么将 $4$ 放在 $3$ 前面， $3,2$ 放在 $1$ 前面。

int l[N],r[N];
priority_queue<int,vector<int>,greater<int>> q;
priority_queue<int> num;
inline void remove(int cur)
{
    vis[cur] = 0;
    r[ l[cur] ]=r[cur];
    l[ r[cur] ]=l[cur];
    int x = l[cur], y = r[cur];
    if (a[x]<a[y]) q.push(x);
}
inline void Case_Test()
{
    cin>>n>>k;
    vector<int> ans;
    while (!q.empty()) q.pop();
    for (int i = 1; i <= n ;i++)
    {
        l[i] = i-1, r[i] = i+1;
        cin>>a[i];
        vis[i] = 1;
    }
    a[0] = inf, a[n+1] = -inf;
    r[0] = 1, l[n+1] = 1;
    l[1] = 0, r[n+1] = 0;
    for (int i=1;i<=n;i++)
        if (a[i]<a[i+1])
            q.push(i);//首先计算逆序对，进队等待操作
    while (k--)
    {
        if (q.empty()) break;
        int cur = q.top();q.pop();//取出进行链表操作
        remove(cur);
        num.push(a[cur]);
    }
    int pos = n+1, pre = 0;
    for (int i=1;i<=n;i++)
    {
        if (!vis[i]) continue;
        if (a[i]<pre) {pos = i;break;}
        else
        {
            ans.push_back(a[i]);
            pre = a[i];
        }
    }
    for (int i=pos;i<=n;i++)
    {
        if (!vis[i]) continue;
        while (!num.empty() && num.top()>a[i])
        {
            ans.push_back(num.top());
            num.pop();
        }
        ans.push_back(a[i]);
    }
    while (!num.empty())
    {
        ans.push_back(num.top());
        num.pop();
    }//还没有插完
    for (int i=0;i<ans.size();i++) 
        cout<<ans[i]<<" \n"[i+1==ans.size()];
}