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()];
}