自动搬运

查看原文

来自洛谷，原作者为

	x_angelkawaii_x **

搬运于2025-08-24 22:21:36，当前版本为作者最后更新于2020-05-05 14:53:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

• 子任务 $1$

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

• 子任务 $2$

$T=1,c=n$，只有一组方案且所有点上都设置了采集器

首先，点集中的 $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();
	}
}