A. The Monster

判断一个括号序列是否合法，可以将左括号视为 1，右括号视为 -1，那么当且仅当它每一个前缀的和都非负且总和为 0，这个括号序列才是合法的。现在加入了通配字符，则枚举左端点并扫描右端点，同时维护前缀和的范围 [l,r] ，若有一刻 r<0 则退出，否则若 l=0 则当前区间为一个合法子区间。

B. MADMAX

典型的单个组合游戏博弈模型。记 f(i,j,k)=0/1 表示先手在点 i 上，后手在点 j 上，当前走过的最大字符是 k 时先手必胜/必败。按拓扑序转移即可。

D. Stranger Trees

第一次听说矩阵树定理还有带权的版本。。把平时用作生成树计数的基尔霍夫矩阵做一些修改，其中邻接矩阵改为边权矩阵，度数矩阵改为与一点相邻的边权和。这样算出来的行列式就是这张图所有生成树的边权乘积之和。

然而这样我们还是无法统计有多少条边与原树重合。考虑建一个完全图，其中原树边的权值赋为 x，其他边的权值赋为 1。这个图的基尔霍夫矩阵消掉一行一列后求出来的行列式是一个 n-1 次多项式，设为 F(x)。则

我们不能直接高斯消元求这个多项式，但我们知道它的次数，于是可以代入 n 个值去插这个多项式。这样一共要做 n 次 O(n^3) 的高斯消元，所以复杂度是 O(n^4) 的。

附：拉格朗日插值求多项式系数

我们发现现在的目标不是代入求一个值，而是要求多项式的每个系数。虽然可以用快速插值做到 O(n\log^2 n)，但不够实用。下面提供一个 O(n^2) 的做法。

对于拉格朗日插值公式，考虑每个 F(i) 对每个系数的贡献：

发现对固定的 i ，F(i) 和右边求积的分母都是常数，分子是个 n-1 次多项式，可以表示为 \frac{\prod_{j=1}^{n}x-j}{x-i}。于是我们可以 O(n^2) 预处理出 \prod_{j=1}^{n}x-j 并每次 O(n) 除掉 x-i。这样就求得了每个 F(i) 的贡献了。

本题代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=110;
const int P=1E9+7;
int qpow(int n, int k)
{
    int r=1;
    while (k)
    {
        if (k&1) r=1ll*r*n%P;
        n=1ll*n*n%P; k>>=1;
    }
    return r;
}
struct Matrix
{
    int a[MAXN][MAXN];
    int det(int n)
    {
        int ans=1;
        for (int i=1; i<n; i++)
        {
            if (a[i][i]==0)
            {
                int p=i;
                for (int j=i; j<n; j++)
                    if (a[j][i]!=0) { p=i; break; }
                swap(a[i], a[p]);
                ans=(-ans+P)%P;
            }
            int r=qpow(a[i][i], P-2);
            for (int j=i+1; j<n; j++)
            {
                int t=1ll*a[j][i]*r%P;
                for (int k=i; k<n; k++)
                    a[j][k]=(a[j][k]-1ll*t*a[i][k]%P+P)%P;
            }
            ans=1ll*ans*a[i][i]%P;
        }
        return ans;
    }
} T, G;
int v[MAXN], h[MAXN], t[MAXN], f[MAXN];
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for (int i=1; i<n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        T.a[u][v]=T.a[v][u]=1;
    }
    for (int x=1; x<=n; x++)
    {
        for (int i=1; i<=n; i++)
        {
            G.a[i][i]=0;
            for (int j=1; j<=n; j++)
                if (i!=j)
                {
                    G.a[i][j]=T.a[i][j]?P-x:P-1;
                    G.a[i][i]+=T.a[i][j]?x:1;
                }
        }
        v[x]=G.det(n);
    }
    h[0]=1;
    for (int i=1; i<=n; i++)
        for (int j=n; j>=0; j--)
        {
            h[j]=(-1ll*i*h[j]%P+P)%P;
            if (j>0) h[j]=(h[j]+h[j-1])%P;
        }
    for (int i=1; i<=n; i++)
    {
        int q=1;
        for (int j=1; j<=n; j++)
            if (j!=i) q=1ll*q*(i-j+P)%P;
        q=qpow(q, P-2);
        int r=qpow(-i+P, P-2);
        for (int j=0; j<=n; j++)
        {
            t[j]=h[j];
            if (j>0) t[j]=(t[j]-t[j-1]+P)%P;
            t[j]=1ll*t[j]*r%P;
        }
        for (int j=0; j<n; j++)
            f[j]=(f[j]+1ll*v[i]*q%P*t[j])%P;
    }
    for (int i=0; i<n; i++) printf("%d ", f[i]);
    putchar('\n');
    return 0;
}