题解 P6527 【「Wdoi-1」幻能采集】

x_angelkawaii_x · 2020-05-05 14:53:52 · 题解

子任务 1

暴力搜索即可，期望得分 10 分

子任务 2

首先，点集中的 $k$ 个点对"聚焦点"产生代价等价转化为 "聚焦点"出发选择 $k$ 条不经过重边的路径长度的乘积。所以一个点的总代价等于从该点出发任选 $k$ 条无重边路径的长度乘积之和。先只考虑子树，假设在计算 $u$ 点的答案，dfs 到以 $v$ 为根的子树，用 $f_i(0 \le i \le k)$ 表示在 $v$ 子树之前的子树中选择 $i$ 条路径相乘的和，$g$ 表示在 $v$ 子树中选择一条路径长度的和，那么可以这样用 $g$ 更新 $f_i

f[u][0]=1;
for(int i=0;i<k;++i)f[u][i+1]+=f[u][i]*g;

之后考虑换根，从 u 父亲 fa 的 f[fa][1] 中扣去从 fa 出发经过 u 的路径贡献即可作为新的 g 参与计算。

复杂度 \mathcal{O}(Tkn)，期望得分 25 分

子任务 4

考虑建立虚树，那么我们需要讨论的点有三种：虚树的结点，虚树上被压缩的二度点，不在虚树上的点

对于虚树上的结点， dp 方式与子任务 1 类似，此处不再赘述

由于 D=0，即不强制在线，所以我们可以用一个小 trick，即将查询点也当做关键点(称设置了采集器的结点为关键点)跑虚树，这样对答案不产生影响还避免了分类讨论

复杂度 \mathcal{O}(qk\log n)，期望得分 50 分

子任务 5

询问强制在线。

如何判断虚树外的点？记查询点 x 在虚树中的 dfs序后继为 v ，则当且仅当 v 不在 x 子树中时 x 为虚树外的点，此时 x 的答案为 0。

若 x 既不是虚树结点也不是虚树外的点，则判定 x 为二度点，记其 dfs序前驱后继为 u,v，则该点答案如下

F[x][2]=(F[u][1]-f[v][1]-siz[v]*d(u,v)+(c-siz[v])*d(u,x))*(f[v][1]+siz[v]*d(x,v))

其中，F[x] 表示换根后的答案数组，f[x] 表示换根前的答案数组，siz[x] 表示 x 的子树中关键点的个数。

时间复杂度 \mathcal{O}(qk\log n)，空间复杂度 \mathcal{O}(nk)，期望得分 70 分

子任务 6

1 \le k\le n

先考虑如何在空间摆脱 k\le 100 的限制，注意到 dp 过程中每个点的 f[u][i] 数组只有 i\le du[u] 时有意义(du[u] 表示 u 的度)，那么通过开 n 个动态数组即可实现空间 O(n)

但是如果按照原形式 dp，时间复杂度是 du^2 相关的，并不能通过菊花图的数据。

观察发现，对于点 u 来说，假设其向各棵子树(包括父子树)出发的路径长度和分别为 g_1,g_2,...,g_m，则答案就是在这 m 个数中选择 1,2,...,k 个数相乘的所有方案之和

所以询问可以被化简：n 个数中选择 k 个数乘积的方案和为多少？

记 f_{l,r,k} 表示 [l,r] 中选择 k 个数的方案和，mid=\frac{l+r}{2}，则有

f_{l,r,k}=\sum_{i=0}^{r-l+1}f_{l,mid,i}*f_{mid+1,r,r-l+1-i}

明显为卷积形式，使用NTT优化即可实现时间 \mathcal{O}(n\log ^2n)，空间 \mathcal{O}(n\log n)，可以通过本题

code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<cstring>
using namespace std;
const int maxn=2e5+5,mod=998244353,maxk=105;
typedef long long ll;
int n;
int siz[maxn],son[maxn],fa[maxn],tp[maxn],dep[maxn],dfn[maxn],tot,bck[maxn];
struct ed{int to,w;};
vector<ed>e1[maxn];vector<int>e2[maxn];set<int>df;
void dfs1(int u)
{
    siz[u]=1;
    for(int i=0,l=e1[u].size();i<l;++i)
    {
        int v=e1[u][i].to;
        if(dep[v])continue;
        dep[v]=(dep[u]+e1[u][i].w)%mod,fa[v]=u;
        dfs1(v);siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int topf)
{
    tp[u]=topf;dfn[u]=++tot;bck[tot]=u;
    if(!son[u])return;
    dfs2(son[u],topf);
    for(int i=0,l=e1[u].size();i<l;++i)
    {
        int v=e1[u][i].to;
        if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
int lca(int x,int y)
{
    while(tp[x]!=tp[y])
    {
        if(dep[tp[x]]<dep[tp[y]])x^=y^=x^=y;
        x=fa[tp[x]];    
    }
    return dep[x]<dep[y]?x:y;
}
inline int dis(int x,int y){return (dep[x]+dep[y]-(dep[lca(x,y)]<<1)+mod)%mod;}
int p[maxn],st[maxn],top,c,k,D;
bool cmp(const int &a,const int &b){return dfn[a]<dfn[b];}
void ins(int u)
{
    if(top==1){st[++top]=u;return;}
    int ff=lca(u,st[top]);
    if(ff==st[top]){st[++top]=u;return;}
    for(;dfn[st[top-1]]>=dfn[ff];--top)e2[st[top-1]].push_back(st[top]);    
    if(ff!=st[top])e2[ff].push_back(st[top]),st[top]=ff;
    st[++top]=u; 
}
namespace Poly
{
    const int maxm=200005;
    const int mod=998244353;
    typedef long long ll;
    int q;bool fl;
    int rev[maxm*4],bin[1<<21];
    inline int fastpow(int x,int y,int P)
    {
        int ans=1;
        for(;y;y>>=1,x=(ll)x*x%P) if(y&1) ans=(ll)ans*x%P;
        return ans;
    }
    inline void NTT(int *a,int n,int f)
    {
        int l=bin[n];
        for(int i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
        for(int i=0;i<n;i++) if(i<rev[i]) std::swap(a[i],a[rev[i]]); 
        for(int i=1;i<n;i<<=1)
        {
            int wn=fastpow(3,~f?(mod-1)/(i<<1):(mod-1)-(mod-1)/(i<<1),mod);
            for(int j=0;j<n;j+=(i<<1))
            {
                int w=1;
                for(int k=0;k<i;k++,w=(ll)w*wn%mod)
                {
                    int x=a[j+k],y=(ll)a[i+j+k]*w%mod;
                    a[j+k]=(x+y)%mod,a[i+j+k]=(x-y+mod)%mod;
                }
            }
        }
        if(f==-1)
        {
            int inv=fastpow(n,mod-2,mod);
            for(int i=0;i<n;i++) a[i]=(ll)a[i]*inv%mod;
        }
    }
    int n,val[maxm],A[21][maxm*4],f1[maxm*4],f2[maxm*4],b1[21][maxm*4],b2[21][maxm*4];
    void solve(int l,int r,int id)
    {
        if(l>=r)
        {
            A[id][0]=1,A[id][1]=val[l];
            return;
        }
        int mid=(l+r)>>1,len=(r-l+1);
        int m=1;
        while(m<=2*len) m<<=1;
        solve(l,mid,id+1);
        for(int i=0;i<=mid-l+1;i++) b1[id][i]=A[id+1][i],A[id+1][i]=0;
        solve(mid+1,r,id+1);
        for(int i=0;i<=r-mid;i++) b2[id][i]=A[id+1][i],A[id+1][i]=0;
        for(int i=0;i<=mid-l+1;i++) f1[i]=b1[id][i];
        for(int i=0;i<=r-mid;i++) f2[i]=b2[id][i];
        NTT(f1,m,1),NTT(f2,m,1);
        for(int i=0;i<m;i++) f1[i]=(ll)f1[i]*f2[i]%mod,f2[i]=0;
        NTT(f1,m,-1);
        for(int i=0;i<=len;i++) A[id][i]=f1[i],f1[i]=0;
    }
    int work(int N,vector<int> AA,int K)
    {
        if(!fl){for(int i=0;i<=20;i++)bin[1<<i]=i;fl=1;}
        n=N;for(int i=0;i<n;i++)val[i+1]=AA[i];
        solve(1,n,0);
        int res=0;
        for(int i=2;i<=K;++i)res=(res+A[0][i])%mod;
        return res;
    }
}
vector<int> cxy[maxn];
int f[maxn],F[maxn],sz[maxn],fa2[maxn],as[maxn],zp[maxn];
bool w[maxn];
void Dfs1(int u)
{
    sz[u]=w[u];df.insert(dfn[u]);if(!w[u])w[u]=-1;
    for(int i=0,l=e2[u].size();i<l;++i)
    {
        int v=e2[u][i],w,g;
        Dfs1(v);sz[u]+=sz[v];w=(dep[v]-dep[u]+mod)%mod;
        g=((ll)sz[v]*w%mod+f[v])%mod;f[u]=(f[u]+g)%mod;cxy[u].push_back(g);
    }
    F[u]=f[u];
}
void Dfs2(int u,int ff)
{
    if(u==1)
    {
        as[u]=Poly::work((int)cxy[u].size(),cxy[u],min((int)cxy[u].size(),c));
        for(int i=0,l=e2[u].size();i<l;++i)Dfs2(e2[u][i],u);
        return;     
    }
    int w=(dep[u]-dep[ff]+mod)%mod;fa2[u]=ff;
    int g=((ll)(k-2*sz[u]+mod)*w%mod+f[ff]-f[u]+mod)%mod;
    f[u]=(f[u]+g)%mod;cxy[u].push_back(g);
    as[u]=Poly::work((int)cxy[u].size(),cxy[u],min((int)cxy[u].size(),c));
    for(int i=0,l=e2[u].size();i<l;++i)Dfs2(e2[u][i],u);
}
void Dfs3(int u)
{
    w[u]=f[u]=0;
    for(int i=0,l=e2[u].size();i<l;++i)Dfs3(e2[u][i]);
    e2[u].clear();cxy[u].clear();
}
int calc(int u)
{
    int res=0;
    if(w[u]!=0)return as[u];
    set<int>::iterator it=df.lower_bound(dfn[u]);
    if(it==df.end())return 0;
    int R=bck[*it],L=fa2[R];
    if(dfn[R]>dfn[u]+siz[u]-1)return 0;
    res=((f[L]-F[R]-(ll)sz[R]*(dep[R]-dep[L]+mod)%mod+(ll)(k-sz[R])*(dep[u]-dep[L]+mod)%mod)%mod+mod)%mod;
    res=((ll)res*(F[R]+(ll)sz[R]*(dep[R]-dep[u]+mod)%mod))%mod;
    return res;
}
int main()
{
    scanf("%d%d",&n,&D);
    int u,v,T,q,la=0;
    for(int i=1;i<n;++i)scanf("%d%d%d",&u,&v,&k),e1[u].push_back(ed{v,k}),e1[v].push_back(ed{u,k});
    dep[1]=1,dfs1(1),dfs2(1,1);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&k,&c);
        for(int i=1;i<=k;++i)scanf("%d",&p[i]),w[p[i]]=1; 
        sort(p+1,p+1+k,cmp);
        st[top=1]=1;
        for(int i=(p[1]==1)?2:1;i<=k;++i)ins(p[i]); 
        for(;top>1;--top)e2[st[top-1]].push_back(st[top]);
        Dfs1(1);Dfs2(1,0);
        scanf("%d",&u);
        for(int i=1;i<=u;++i)
        {
            scanf("%d",&v),v=(v+D*la-1)%n+1;
            printf("%d\n",la=calc(v));
        }
        Dfs3(1);df.clear();
    }
}