Codeforces 1111 E. Tree(가상 트리, DP)

제목의 뜻

한 그루의 나무, q개의 문의가 있는데 매번 문의할 때마다 한 점을 지정하여 나무 뿌리를 만들고 k개의 점을 주어 이 점들을 m조를 초과하지 않는 방안수로 나누도록 요구한다. 분배의 제한은 조상 관계가 있는 두 개의 점을 같은 조로 나누면 안 된다.제목은 모든 질문의 k를 합치면 1e5를 넘지 않는다는 것을 보증한다.

사고의 방향

만약에 원수에 직접 DP계수를 한다면 q번 문의한 DP의 총 복잡도는 제곱급이고 분명히 옳지 않다.질문 포인트의 총계가 매우 적기 때문에 허수에서 계산하는 것을 고려한다.(허수를 잘 모르는 사람은 먼저 배울 수 있다. 질문의 지점에 따라 관건적인 정보를 포함하지만 규모가 작은 나무를 재건한다는 생각일 것이다) 그래서 여러 번 물어본 문제가 해결되었다.어려운 점은 빈 나무의 dp계수를 고려하는 것으로 바뀌었다.우리는 dfs 순서에 따라 dp를 정의하여 f[i][j]는 누적된 전 i개의 점을 j조로 나누는 방안수를 표시하고, cnt[i]는 점 i에서 뿌리까지 몇 개의 질문점이 있는지 나타낸다.그러면 f[i][j]: ① 만약에 j<=cnt[i]라면 i의 조상들을 분리하는 것만으로도 j개 조를 사용해야 한다는 뜻이다. 그러면 이때 i는 반드시 조를 놓을 수 없다. 즉, 이때 방안이 통하지 않는다는 것이다. 그래서 f[i][j]=0;② 그렇지 않으면 f[i][j]=f[i-1][j-1]+f[i-1][j]*(j-cnt[i]).이것은 이해하기 어렵지 않을 것이다. 우리는 dfs 순서에 따라 dp를 만들었는데 dp가 점 i에 이르렀을 때 그의 조상은 반드시 이미 갱신을 끝냈을 것이다.그러면 새로 온 점 i에 대해 새로운 그룹을 열거나 방안 수는 f[i-1][j-1]이거나 기존 그룹에 가입하거나 방안 수는 f[i-1][j]*(j-cnt[i])이다. (즉 기존 그룹에서 조상들이 있던 그룹을 제거하는 것이다).공간이 좀 빡빡하다는 것을 감안하여 dp를 굴릴 수 있다. 물론 꼼꼼하게 계산할 수 있고 2차원 그룹을 만들어서 DP의 공간도 충분하다.

코드

#include
#define dd(x) cout< P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=1e5+10,INF=0x3f3f3f3f,mod=1e9+7;
vector G[maxn],g[maxn];
int fa[maxn][32],dep[maxn],dfn[maxn],id;
void dfs(int u,int f)
{
    dep[u]=dep[f]+1;
    dfn[u]=++id;
    fa[u][0]=f;
    for (int i=1;i<=25;++i)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for (auto& v:G[u])
    {
        if (v==f)
            continue;
        dfs(v,u);
    }
}
int LCA(int x,int y)
{
    if (dep[x]>i)&1)
            x=fa[x][i];
    if (x==y)
        return x;
    for (int i=25;i>=0;--i)
        if (fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int s[maxn],top;
int a[maxn];
bool isqry[maxn];
void build(int n)
{
    top=0;
    for (int i=0;i=0&&a[i]==a[i-1])
            continue;
        int u=a[i];
        if (!top)
        {
            s[++top]=u;
            continue;
        }
        int lca=LCA(u,s[top]);
        while (top>1&&dfn[lca]<=dfn[s[top-1]])
            g[s[top-1]].pb(s[top]),g[s[top]].pb(s[top-1]),--top;
        if (lca!=s[top])
            g[lca].pb(s[top]),g[s[top]].pb(lca),s[top]=lca;
        s[++top]=u;
    }
    while (top>1)
        g[s[top-1]].pb(s[top]),g[s[top]].pb(s[top-1]),--top;
}
ll f[500];
void cal(int u,int ff,int cnt,int m)
{
    if (isqry[u])
    {
        for (int i=m;i>=0;--i)
        {
            if (i<=cnt)
                f[i]=0;
            else
                f[i]=(f[i-1]+f[i]*(i-cnt)%mod)%mod;
        }
    }
    for (auto& v:g[u])
    {
        if (v==ff)
            continue;
        cal(v,u,cnt+isqry[u],m);
    }
    g[u].clear();
    isqry[u]=0;
}
int main()
{
    int n,q;
    cin>>n>>q;
    for (int i=1;i