福泉市自己的网站,百度标注平台怎么加入,专业团队搞笑图片,中国上海网HDU 6643 Ridiculous Netizens
problem
hdu6643
题目大意#xff1a;给定一棵无根树#xff0c;以及每个点的点权 wiw_iwi。
定义一个连通块的价值为连通块内点的点权之积。
求有多少个连通块价值 ≤m\le m≤m。 n≤2e3,m≤1e6n\le 2e3,m\le 1e6n≤2e3,m≤1e6。
solu…HDU 6643 Ridiculous Netizens
problem
hdu6643
题目大意给定一棵无根树以及每个点的点权 wiw_iwi。
定义一个连通块的价值为连通块内点的点权之积。
求有多少个连通块价值 ≤m\le m≤m。
n≤2e3,m≤1e6n\le 2e3,m\le 1e6n≤2e3,m≤1e6。
solution
取一个点作根将无根树转化为有根树。
统计连通块包含根节点的情况不包含根就分裂成若干个互不相同的子树变成子问题重复以上操作。
选取重心作根点分治。
这是大致框架问题就在于怎么快速计算包含根的符合要求的连通块个数。
observation因为是连通块如果父亲不选那么其所有子孙都不可能入选。
所以我们考虑使用 dfn 序重编号从后往前做。
设 dpi,j:dfndp_{i,j}:dfndpi,j:dfn 序编号到为 iii 的点为止价值为 jjj 的连通块个数。 如果要选当前点子孙是可选可不选的从 dfndfndfn 序后一个直接转移。 【dfn[i]:dfndfn[i]:dfndfn[i]:dfn 序为 iii 的原对应点】 dp(i,j×wdfn[i])←dp(i1,j)dp(i,j\times w_{dfn[i]})\leftarrow dp(i1,j)dp(i,j×wdfn[i])←dp(i1,j) 如果不选就必须跳过其所有子孙。【siz[i]:isiz[i]:isiz[i]:i 子树的大小】 dp(i,j)←dp(isizi,j)dp(i,j)\leftarrow dp(isiz_i,j)dp(i,j)←dp(isizi,j)
注意到 nmnmnm 的范围根本开不下 2e92e92e9 的数组。
那就——分块
按照连通块价值的大小分块 ≤m\le\sqrt{m}≤m 和 m\sqrt{m}m。 ≤m\le \sqrt{m}≤m 设 fi,j:f_{i,j}:fi,j: 到 iii 为止价值为 jjj 的连通块个数。 正常地向上面一样进行背包转移。 m\sqrt{m}m 设 fi,j:f_{i,j}:fi,j: 到 iii 为止价值还能装下 jjj 的连通块个数。即价值已经为 mj\frac{m}{j}jm 的联通块个数。
具体可见代码实现。
code
#include cmath
#include cstdio
#include cstring
#include iostream
using namespace std;
#define maxn 2005
#define maxm 1005
#define int long long
#define mod 1000000007
#define inf 0x7f7f7f7f
struct node { int to, nxt; }E[maxn 1];
int cnt, tot, n, m, Max, N, M, T, root, ans;
bool vis[maxn];
int w[maxn], siz[maxn], dfn[maxn], head[maxn];
int f[maxn][maxm], g[maxn][maxm];void addedge( int u, int v ) {E[tot] { v, head[u] }, head[u] tot ;E[tot] { u, head[v] }, head[v] tot ;
}void get_root( int u, int fa ) {int maxson 0; siz[u] 1;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( vis[v] or v fa ) continue;get_root( v, u );siz[u] siz[v];maxson max( maxson, siz[v] );}maxson max( maxson, N - siz[u] );if( maxson Max ) Max maxson, root u;
}void dfs( int u, int fa ) {dfn[ cnt] u, siz[u] 1;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( v fa or vis[v] ) continue;else dfs( v, u ), siz[u] siz[v];}
}void calc() {cnt 0, dfs( root, 0 );for( int i 1;i cnt 1;i ) {memset( f[i], 0, sizeof( f[i] ) );memset( g[i], 0, sizeof( g[i] ) );} f[cnt 1][1] 1;for( int i cnt;i;i -- ) {int x w[dfn[i]];//要选dfn[i]for( int j 1;j min( M, m / x );j ) { //枚举后i1个一共使用了j空间 如果后i个乘积不超过M 做普通背包int k j * x;if( k M ) f[i][k] ( f[i][k] f[i 1][j] ) % mod;else g[i][m / k] ( g[i][m / k] f[i 1][j] ) % mod;//否则就是剩下了m/(j*x)的贡献//这里是用的f[i1][j]在更新 只代表了后i1乘积不超过M的情况}for( int j x;j M;j )//这里使用的g[i1][j]在更新 只代表了后i1乘积超过M的情况g[i][j / x] ( g[i][j / x] g[i 1][j] ) % mod;//不选for( int j 1;j M;j ) {f[i][j] ( f[i][j] f[i siz[dfn[i]]][j] ) % mod;g[i][j] ( g[i][j] g[i siz[dfn[i]]][j] ) % mod;}}for( int i 1;i M;i )ans ( ans f[1][i] g[1][i] ) % mod;ans ( ans - 1 mod ) % mod; //减去空连通块的贡献
}void dfs( int u ) {vis[u] 1;calc();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( vis[v] ) continue;Max inf, N siz[v];get_root( v, u );dfs( root );}
}signed main() {scanf( %lld, T );while( T -- ) {tot 0; memset( head, -1, sizeof( head ) );scanf( %lld %lld, n, m );for( int i 1;i n;i ) vis[i] 0, scanf( %lld, w[i] );for( int i 1, u, v;i n;i ) {scanf( %lld %lld, u, v );addedge( u, v );}M sqrt( m );Max inf, N n;get_root( 1, 0 );dfs( root );printf( %lld\n, ans );ans 0;}return 0;
}
