Orz ylh.

A. 后缀树 suffix

显然如果确定了第一个字符，那么后面的字符都不能取第一个字符，然后就没有其他限制了。答案为 26\times 25^{n-1} 。

B. 纯粹容器 senpai

先枚举每个容器。然后考虑 DP ，f(i,j,k) 表示目前出了该容器还有 i 个容器没有被打倒，该容器左右分别有 j 个和 k 个比他弱的容器，预处理逆元后可以 O(1) 转移。记忆化后可以做到 O(n^3)。代码：

#include <cstdio>
#include <cstring>
const int MAXN=55;
const int P=998244353;
int n, a[MAXN], inv[MAXN];
int f1[MAXN][MAXN][MAXN];
int f2[MAXN][MAXN];
int dp1(int n, int p, int q)
{
    if (~f1[n][p][q]) return f1[n][p][q];
    if (p==0||q==0) return f1[n][p][q]=0;
    int res=(1ll*p*dp1(n-1, p-1, q)+1ll*q*dp1(n-1, p, q-1))%P;
    if (p+q<n) res=(res+1ll*(n-p-q)*dp1(n-1, p, q))%P;
    return f1[n][p][q]=(1ll*res*inv[n]+1)%P;
}
int dp2(int n, int m)
{
    if (~f2[n][m]) return f2[n][m];
    if (m==0) return f2[n][m]=0;
    int res=1ll*m*dp2(n-1, m-1)%P;
    if (m<n) res=(res+1ll*(n-m)*dp2(n-1, m))%P;
    return f2[n][m]=(1ll*res*inv[n]+1)%P;
}
int main()
{
//  freopen("B.in", "r", stdin);
//  freopen("B.out", "w", stdout);
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    inv[1]=1;
    for (int i=2; i<=n; i++) inv[i]=1ll*(P-P/i)*inv[P%i]%P;
    memset(f1, -1, sizeof f1);
    memset(f2, -1, sizeof f2);
    for (int i=1; i<=n; i++)
    {
        int p, q;
        for (p=i; p>=1&&a[p]<=a[i]; p--);
        for (q=i; q<=n&&a[q]<=a[i]; q++);
        if (p!=0&&q!=n+1) printf("%d ", (dp1(n-1, i-p, q-i)-1+P)%P);
        else if (p!=0&&q==n+1) printf("%d ", (dp2(n-1, i-p)-1+P)%P);
        else if (p==0&&q!=n+1) printf("%d ", (dp2(n-1, q-i)-1+P)%P);
        else printf("%d ", n-1);
    }
    return 0;
}

C. 丝之割 silksong

这把琴看着很难受，先把上方支柱的点反转，那么问题就是求用点对 (i,j) 覆盖所有给出的 (u,v)(u<i,v<j) 的最小代价。

如果选取的两个点对 (i_1,j_1),(i_2,j_2) 满足 (i_1\leq i_2,j_1\leq j_2) ，那么显然前者是没有任何意义的，所以答案中不会存在这样的点对。所以每个选取的 (i,j) 必须覆盖 u<i 的所有弦，否则后面就没有机会覆盖了。

考虑 DP ，f(i) 表示最后一个上方支柱选的是 i 的点对。有转移 f(i)=\min f(j)+a_ig_j ，其中 g_j 表示 u\geq j 的弦中最小的 b 。不难看出 g_j 单调递减，求出 a_i 的凸包就可以斜率优化了，复杂度 O(n) 。

代码：

#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN=330000;
const int INF=1E9;
const ll LINF=1E18;
int a[MAXN], b[MAXN];
int s[MAXN], q[MAXN];
vector<int> c[MAXN];
ll f[MAXN];
int g[MAXN], h[MAXN];
inline ll gety(int i, int j)
{
    return f[j]-f[i];
}
inline int getx(int i, int j)
{
    return g[s[i]]-g[s[j]];
}
int main()
{
//  freopen("C.in", "r", stdin);
//  freopen("C.out", "w", stdout);
    int n, m, p=0;
    scanf("%d%d", &n, &m);
    for (int i=n; i>=1; i--) scanf("%d", &a[i]);
    for (int i=1; i<=n; i++) scanf("%d", &b[i]);
    for (int i=1; i<=m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        c[n-u+1].push_back(v);
    }
    for (int i=1; i<=n; i++)
    {
        while (p>0&&a[i]<=a[s[p]]) p--;
        s[++p]=i;
    }
    h[n+1]=INF;
    for (int i=n; i>=1; i--)
        h[i]=min(h[i+1], b[i]);
    for (int i=n, k=0; i>=0; i--)
    {
        for (int j:c[i]) k=max(k, j);
        g[i]=h[k+1];
    }
    int cl=0, op=0; q[cl++]=0;
    for (int i=1; i<=p; i++)
    {
        while (cl-op>=2&&gety(q[op+1], q[op])>=1ll*a[s[i]]*getx(q[op+1], q[op])) op++;
        f[i]=f[q[op]]+1ll*a[s[i]]*g[s[q[op]]];
        while (cl-op>=2&&gety(i, q[cl-1])*getx(q[cl-1], q[cl-2])<=gety(q[cl-1], q[cl-2])*getx(i, q[cl-1])) cl--;
        q[cl++]=i;
    }
    ll ans=LINF;
    int t;
    for (t=n; t>=0&&c[t].empty(); t--);
    for (int i=p; i>=0&&s[i]>t; i--) ans=min(ans, f[i]);
    printf("%lld\n", ans);
    return 0;
}

D. 最优性剪枝 search

根据期望的线性性，期望访问的节点数 = \sum_{i=1}^{n}x_i ，x_i 表示节点 i 被访问的概率。

设节点 u 的深度为 d_u，子树 u 中最浅的叶子节点的深度为 h_u。 可以发现 x_i 只与 i 的祖先有关，祖先 u 不能在访问 i 所在子树前访问 h_v<d_u 的子树。设这样的子树有 l 个，可以得出 u 的贡献为 \frac{1}{l+1}。

从上往下 DFS ，考虑维护当前节点到根的路径上的节点对每个深度的贡献。将 u 的子树按 h_v 排序，从第 i 个儿子切换到第 i+1 个儿子会使区间 (h_{v_i},h_{v_{i+1}}] 的贡献乘上 \frac{i}{i+1}。用树状数组维护乘法差分标记即可。代码：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN=330000;
const int P=998244353;
int n, inv[MAXN];
struct BIT
{
    int s[MAXN];
    int lb(int x) { return x&-x; }
    void init()
    {
        for (int i=1; i<=n; i++) s[i]=1;
    }
    void mul(int x, int k)
    {
        while (x<=n)
        {
            s[x]=1ll*s[x]*k%P;
            x+=lb(x);
        }
    }
    int query(int x)
    {
        int r=1;
        while (x>0)
        {
            r=1ll*r*s[x]%P;
            x-=lb(x);
        }
        return r;
    }
} bit;
int fa[MAXN];
vector<int> son[MAXN];
int d[MAXN], h[MAXN], ans;
bool cmp(int a, int b)
{
    return h[a]<h[b];
}
void dfs(int u)
{
    ans=(ans+bit.query(d[u]-1))%P;
    for (int i=0; i<son[u].size(); i++)
    {
        bit.mul(h[son[u][i]], inv[i+1]);
        if (i+1<son[u].size())
            bit.mul(h[son[u][i+1]], i+1);
    }
    for (int i=0; i<son[u].size(); i++)
    {
        int v=son[u][i]; dfs(v);
        bit.mul(h[v], 1ll*(i+1)*inv[i+2]%P);
        if (i+1<son[u].size())
            bit.mul(h[son[u][i+1]], 1ll*inv[i+1]*(i+2)%P);
    }
    for (int i=0; i<son[u].size(); i++)
    {
        bit.mul(h[son[u][i]], i+2);
        if (i+1<son[u].size())
            bit.mul(h[son[u][i+1]], inv[i+2]);
    }
}
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    scanf("%d", &n);
    d[1]=1; h[1]=n;
    for (int i=2; i<=n; i++)
    {
        scanf("%d", &fa[i]);
        son[fa[i]].push_back(i);
        d[i]=d[fa[i]]+1; h[i]=n;
    }
    for (int i=n; i>=1; i--)
    {
        if (son[i].empty()) h[i]=d[i];
        h[fa[i]]=min(h[fa[i]], h[i]);
        sort(son[i].begin(), son[i].end(), cmp);
    }
    inv[1]=1;
    for (int i=2; i<=n; i++)
        inv[i]=1ll*(P-P/i)*inv[P%i]%P;
    bit.init(); ans=0; dfs(1);
    printf("%d\n", ans);
    return 0;
}