HDU 6643 Ridiculous Netizens

problem

hdu6643

題目大意：給定一棵無根樹，以及每個點的點權 $w_i$。

定義一個連通塊的價值為連通塊內點的點權之積。

求有多少個連通塊價值 $\le m$。

$n\le 2e3,m\le 1e6$。

solution

取一個點作根，將無根樹轉化為有根樹。

統計連通塊包含根節點的情況，不包含根就分裂成若干個互不相同的子樹，變成子問題，重復以上操作。

選取重心作根，點分治。

這是大致框架，問題就在于怎么快速計算包含根的符合要求的連通塊個數。

observation：因為是連通塊，如果父親不選，那么其所有子孫都不可能入選。

所以我們考慮使用 dfn 序重編號，從后往前做。

設 $d{p}_{i,j}:dfn$ 序編號到為 $i$ 的點為止，價值為 $j$ 的連通塊個數。

• 如果要選當前點，子孫是可選可不選的，從 $dfn$ 序后一個直接轉移。

  【$dfn[i]:dfn$ 序為 $i$ 的原對應點】

  $dp(i,j\times w_{dfn[i]})\leftarrow dp(i+1,j)$

• 如果不選，就必須跳過其所有子孫。【$siz[i]:i$ 子樹的大小】

  $dp(i,j)\leftarrow dp(i+si{z}_i,j)$

注意到 $nm$ 的范圍，根本開不下 $2e9$ 的數組。

那就——分塊！

按照連通塊價值的大小分塊， $\le \sqrt{m}$ 和 $>\sqrt{m}$。

• $\le \sqrt{m}$

  設 $f_{i,j}:$ 到 $i$ 為止，價值為 $j$ 的連通塊個數。

  正常地向上面一樣進行背包轉移。

• $>\sqrt{m}$

  設 $f_{i,j}:$ 到 $i$ 為止，價值還能裝下 $j$ 的連通塊個數。即價值已經為 $\frac{m}{j}$ 的聯通塊個數。

具體可見代碼實現。

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 ++ ) { //枚舉后i+1個一共使用了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[i+1][j]在更新 只代表了后i+1乘積不超過M的情況}for( int j = x;j <= M;j ++ )//這里使用的g[i+1][j]在更新 只代表了后i+1乘積超過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; }

總結

以上是生活随笔為你收集整理的[HDU 6643] Ridiculous Netizens（点分治+根号分治+dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。