自动搬运

查看原文

来自洛谷，原作者为

	Great_Influence **

搬运于2025-08-24 22:08:36，当前版本为作者最后更新于2019-03-05 15:11:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

暴力能 A 的迷之题目。

题意可以理解为给你几棵小树，然后将这几颗小树连成一个环，使得环长 $\ge Y$ ，求满足要求的树个数。

因为数据范围很小，考虑直接用 $dfs$ 将每棵小树内的所有路径都统计出来。然后就变成了问给你几个集合，从这些集合中每个集合选择一个数，问和 $\ge Y$ 的方案和。这是一个简单背包问题。求方案和可以顺便求出。

具体来说，设 $dp[i][0/1]$ 表示 和为 $i$ 的方案数/方案和， $g[i][0/1]$ 表示当前小树内长度为 $i$ 的路径数/长度和，则存在转移:

$$dp[i+j][0]\leftarrow dp[i][0]*g[j][0]$$ $$dp[i+j][1]\leftarrow dp[i][0]*g[j][1] + dp[i][1]*g[j][0] $$

直接转移即可。

注意我们并不关注这个长度具体是多少，只关注它是否比 $Y$ 大。并且长度大于等于 $Y$ 的方案之后再怎么变都是满足要求的。因此可以将长度 $\ge Y$ 的部分记在一起。还有个优化是可以直接从 $X*k$ 开始转移。还有就是只转移 $g$ 和 $dp$ 有值的位置。

时间复杂度为 $O(\sum n_i^2+\min\{Y,n_i^2\}(Y-XK))=O(NY\sqrt{Y})$ ， $n_i$ 为第 $i$ 棵小树的点数。复杂度证明为考虑子树贡献，当 $\forall i,Y=n_i^2$时复杂度取得最大值。

代码:

#include<bits/stdc++.h>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define pb push_back
#define mx(a,b) (a>b?a:b)
#define mn(a,b) (a<b?a:b)
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;
using namespace std;

namespace IO
{
	const uint32 Buffsize=1<<15,Output=1<<24;
	static char Ch[Buffsize],*S=Ch,*T=Ch;
	inline char getc()
	{
		return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
	}
	static char Out[Output],*nowps=Out;
	
	inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}

	template<typename T>inline void read(T&x)
	{
		x=0;static char ch;T f=1;
		for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
		for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
		x*=f;
	}

	template<typename T>inline void write(T x,char ch='\n')
	{
		if(!x)*nowps++='0';
		if(x<0)*nowps++='-',x=-x;
		static uint32 sta[111],tp;
		for(tp=0;x;x/=10)sta[++tp]=x%10;
		for(;tp;*nowps++=sta[tp--]^48);
		*nowps++=ch;
	}
}
using namespace IO;

void file(void)
{
	FILE*DSD=freopen("water.in","r",stdin);
	FILE*CSC=freopen("water.out","w",stdout);
}

const int MAXN=1500+7,MAXY=2500+7,mod=1e9+7;

static int n,m;

static struct edge
{
	int v,w,nxt;
}p[MAXN<<1];

static int head[MAXN],e;

inline void add(int u,int v,int w)
{p[++e]=(edge){v,w,head[u]},head[u]=e;}

namespace DSU
{
	static int fa[MAXN];

	inline void clear(){Rep(i,1,n)fa[i]=i;}

	inline int Find(int u){return u==fa[u]?u:fa[u]=Find(fa[u]);}
}

static int X,Y;

inline void init()
{
	read(n),read(m),read(X),read(Y);
	DSU::clear();
	static int u,v,w;
	Rep(i,1,m)read(u),read(v),read(w)
		,add(u,v,w),add(v,u,w),DSU::fa[DSU::Find(u)]=DSU::Find(v);
}

static int cn;

static int bel[MAXN],dst[MAXN][MAXY],sig[MAXN][MAXY];

void dftag(int u,int fr,int dir)
{
	bel[u]=dir;
	for(register int i=head[u];i;i=p[i].nxt)
	{
		int v=p[i].v;
		if(v^fr)dftag(v,u,dir);
	}
}

void dffix(int u,int fr,int len)
{
	if(fr)(sig[bel[u]][min(Y,len)]+=len)%=mod,++dst[bel[u]][min(Y,len)];
	for(register int i=head[u];i;i=p[i].nxt)
	{
		int v=p[i].v;
		if(v^fr)dffix(v,u,len+p[i].w);
	}
}

static int dp[MAXY][2],las[MAXY][2];

inline int fac(int u)
{
	register int sm=1;
	Rep(i,2,u)sm=(ll)sm*i%mod;
	return sm;
}

inline void solve()
{
	Rep(i,1,n)if(DSU::Find(i)==i)++cn,dftag(i,0,cn);
	Rep(i,1,n)dffix(i,0,0);
	static int st=min(Y,X*cn);
	dp[st][0]=1,dp[st][1]=X*cn;
	Rep(i,1,cn)
	{
		Rep(j,st,Y)las[j][0]=dp[j][0]
			,las[j][1]=dp[j][1],dp[j][0]=dp[j][1]=0;
		Rep(j,0,Y)if(dst[i][j])Rep(k,st,Y)if(las[k][0])
		{
			dp[min(j+k,Y)][0]=(dp[min(j+k,Y)][0]+
				(ll)las[k][0]*dst[i][j])%mod;

			dp[min(j+k,Y)][1]=(dp[min(j+k,Y)][1]+
				(ll)las[k][0]*sig[i][j]+(ll)las[k][1]*dst[i][j])%mod;
		}
	}
	cout<<(ll)dp[Y][1]*fac(cn-1)%mod*((mod+1)/2)%mod<<endl;
}

int main()
{
	file();
	init();
	solve();
	return 0;
}