HDU 4625. JZPTREE

题目简述：给定$n leq 50000$个节点的数，每条边的长度为$1$，对每个节点$u$，求

$$ E_u = sum_{v=1}^n (d(u, v))^k, $$

其中$d(u, v)$是节点$u$和节点$v$的距离，而$k leq 500$是一个常数。

解1：

由斯特林数的性质，我们注意到

$$ x^n = sum_{k=0}^n egin{Bmatrix} n \ k end{Bmatrix} x^{underline{k}}. $$

从而，

$$ E_u = sum_{v=1}^n (d(u, v))^k = sum_{i=0}^k egin{Bmatrix} k \ i end{Bmatrix} sum_{v=1}^n (d(u, v))^{underline{i}}. $$

为此，我们定义

$$f[u][k] = sum_{v in T_u} (d(u, v))^{underline{k}},$$

其中$T_u$表示以$u$为根节点的子树。令$ ext{son}(u)$表示节点$u$的所有儿子节点的集合，并注意到$(x+1)^{underline{k}} = x^{underline{k}}+kx^{underline{k-1}}$，则

$$
egin{aligned}
f[u][k]
& = sum_{v in ext{son}(u)} sum_{w in T_v} (d(u, w))^{underline{k}} \
& = sum_{v in ext{son}(u)} sum_{w in T_v} (d(v, w)+1)^{underline{k}} \
& = sum_{v in ext{son}(u)} sum_{w in T_v} Big( (d(v, w))^{underline{k}}+k (d(v, w))^{underline{k-1}} Big) \
& = sum_{v in ext{son}(u)} Big( f[v][k]+k f[v][k-1] Big)
end{aligned}
$$

两遍DFS即可求出所有$E_u$，从而可在$O(nk)$的复杂度内解决。

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 typedef long long ll;
  6 typedef unsigned long long ull;
  7 typedef double ld;
  8 typedef pair<int,int> pii;
  9 typedef pair<ll,ll> pll;
 10 typedef pair<ld,ld> pdd;
 11 
 12 #define X first
 13 #define Y second
 14 
 15 //#include <boost/unordered_map.hpp>
 16 //using namespace boost;
 17 
 18 /*
 19 #include <ext/pb_ds/tree_policy.hpp>
 20 #include <ext/pb_ds/assoc_container.hpp>
 21 using namespace __gnu_pbds;
 22 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 23 rbtree T;
 24 */
 25 
 26 namespace io{
 27     const int L = (1 << 20) + 1;
 28 
 29     char buf[L], *S , *T, c;
 30 
 31     char getchar() {
 32         if(__builtin_expect(S == T, 0)) {
 33             T = (S = buf) + fread(buf, 1, L, stdin);
 34             return (S == T ? EOF : *S++);
 35         }
 36         return *S++;
 37     }
 38 
 39     int inp() {
 40         int x = 0, f = 1; char ch;
 41         for(ch = getchar(); !isdigit(ch); ch = getchar())
 42             if(ch == '-') f = -1;
 43         for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
 44         return x * f;
 45     }
 46 
 47     unsigned inpu()
 48     {
 49         unsigned x = 0; char ch;
 50         for(ch = getchar(); !isdigit(ch); ch = getchar());
 51         for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
 52         return x;
 53     }
 54 
 55     ll inp_ll() {
 56         ll x = 0; int f = 1; char ch;
 57         for(ch = getchar(); !isdigit(ch); ch = getchar())
 58             if(ch == '-') f = -1;
 59         for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
 60         return x * f;
 61     }
 62 
 63     char B[25], *outs=B+20, *outr=B+20;
 64     template<class T>
 65     inline void print(register T a,register char x=0){
 66         if(x) *--outs = x, x = 0;
 67 
 68         if(!a)*--outs = '0';
 69         else
 70             while(a)
 71                 *--outs = (a % 10) + 48, a /= 10;
 72 
 73         if(x)
 74             *--outs = x;
 75 
 76         fwrite(outs, outr - outs , 1, stdout);
 77         outs = outr;
 78     }
 79 };
 80 
 81 using io :: print;
 82 using io :: inp;
 83 using io :: inpu;
 84 using io :: inp_ll;
 85 
 86 using i32 = int;
 87 using i64 = long long;
 88 using u8 = unsigned char;
 89 using u32 = unsigned;
 90 using u64 = unsigned long long;
 91 using f64 = double;
 92 using f80 = long double;
 93 
 94 ll power(ll a, ll b, ll p)
 95 {
 96     if (!b) return 1;
 97     ll t = power(a, b/2, p);
 98     t = t*t%p;
 99     if (b&1) t = t*a%p;
100     return t;
101 }
102 
103 ll exgcd(ll a, ll b, ll &x, ll &y)
104 {
105     if (b == 0)
106     {
107         x = 1;
108         y = 0;
109         return a;
110     }
111     ll px, py;
112     ll d = exgcd(b, a%b, px, py);
113     x = py;
114     y = px-a/b*py;
115     return d;
116 }
117 
118 template<class T>
119 inline void freshmin(T &a, const T &b)
120 {
121     if (a > b) a = b;
122 }
123 
124 template<class T>
125 inline void freshmax(T &a, const T &b)
126 {
127     if (a < b) a = b;
128 }
129 
130 const int MAXN = 50010;
131 const int MAXK = 510;
132 const int MOD = 10007;
133 const f80 MI = f80(1)/MOD;
134 const int INF = 100001;
135 
136 int n, k;
137 int S[MAXK][MAXK];
138 
139 vector<int> v[MAXN];
140 int f[MAXN][MAXK], g[MAXN][MAXK];
141 
142 void dfs1(int x, int p)
143 {
144     f[x][0] = 1;
145     for (int i = 1; i <= k; ++ i)
146         f[x][i] = 0;
147     for (auto y : v[x])
148     {
149         if (y == p) continue;
150         dfs1(y, x);
151         (f[x][0] += f[y][0]) %= MOD;
152         for (int i = 1; i <= k; ++ i)
153             (f[x][i] += f[y][i]+i*f[y][i-1]) %= MOD;
154     }
155 }
156 
157 void dfs2(int x, int p)
158 {
159     if (!p)
160     {
161         for (int i = 0; i <= k; ++ i)
162             g[x][i] = f[x][i];
163     }
164     for (auto y : v[x])
165     {
166         if (y == p) continue;
167         g[y][0] = g[x][0];
168         for (int i = 1; i <= k; ++ i)
169         {
170             int g1 = (g[x][i]-(f[y][i]+i*f[y][i-1]))%MOD;
171             int g2 = (g[x][i-1]-(f[y][i-1]+(i-1)*(i-2 >= 0 ? f[y][i-2] : 0)))%MOD;
172             g[y][i] = (f[y][i]+g1+i*g2)%MOD;
173         }
174         dfs2(y, x);
175     }
176 }
177 
178 int main()
179 {
180 
181     S[0][0] = 1;
182     for (int i = 1; i <= 500; ++ i)
183         for (int j = 1; j <= i; ++ j)
184             S[i][j] = (S[i-1][j-1]+S[i-1][j]*j)%MOD;
185 
186     for (int T = inp(); T --; )
187     {
188         n = inp();
189         k = inp();
190         for (int i = 1; i <= n; ++ i)
191             v[i].clear();
192         for (int i = 1; i < n; ++ i)
193         {
194             int x = inp();
195             int y = inp();
196             v[x].push_back(y);
197             v[y].push_back(x);
198         }
199         dfs1(1, 0);
200         dfs2(1, 0);
201         for (int x = 1; x <= n; ++ x)
202         {
203             int ret = 0;
204             for (int i = 0; i <= k; ++ i)
205                 (ret += S[k][i]*g[x][i]) %= MOD;
206             printf("%d
", (ret+MOD)%MOD);
207         }
208     }
209 
210     return 0;
211 }

View Code

解2：

我们用另一个斯特林数的性质：

$$ x^n = sum_{k=0}^n k! egin{Bmatrix} n \ k end{Bmatrix} inom{x}{k}. $$

从而，

$$ E_u = sum_{v=1}^n (d(u, v))^k = sum_{i=0}^k i! egin{Bmatrix} k \ i end{Bmatrix} sum_{v=1}^n inom{d(u, v)}{i}. $$

为此，我们定义

$$f[u][k] = sum_{v in T_u} inom{d(u, v)}{k},$$

其中$T_u$表示以$u$为根节点的子树。令$ ext{son}(u)$表示节点$u$的所有儿子节点的集合，则

$$
egin{aligned}
f[u][k]
& = sum_{v in ext{son}(u)} sum_{w in T_v} inom{d(u, w)}{k} \
& = sum_{v in ext{son}(u)} sum_{w in T_v} inom{d(v, w)+1}{k} \
& = sum_{v in ext{son}(u)} sum_{w in T_v} left( inom{d(v, w)}{k} + inom{d(v, w)}{k-1} ight) \
& = sum_{v in ext{son}(u)} Big( f[v][k]+f[v][k-1] Big)
end{aligned}
$$

两遍DFS即可求出所有$E_u$，从而可在$O(nk)$的复杂度内解决。

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 typedef long long ll;
  6 typedef unsigned long long ull;
  7 typedef double ld;
  8 typedef pair<int,int> pii;
  9 typedef pair<ll,ll> pll;
 10 typedef pair<ld,ld> pdd;
 11 
 12 #define X first
 13 #define Y second
 14 
 15 //#include <boost/unordered_map.hpp>
 16 //using namespace boost;
 17 
 18 /*
 19 #include <ext/pb_ds/tree_policy.hpp>
 20 #include <ext/pb_ds/assoc_container.hpp>
 21 using namespace __gnu_pbds;
 22 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 23 rbtree T;
 24 */
 25 
 26 namespace io{
 27     const int L = (1 << 20) + 1;
 28 
 29     char buf[L], *S , *T, c;
 30 
 31     char getchar() {
 32         if(__builtin_expect(S == T, 0)) {
 33             T = (S = buf) + fread(buf, 1, L, stdin);
 34             return (S == T ? EOF : *S++);
 35         }
 36         return *S++;
 37     }
 38 
 39     int inp() {
 40         int x = 0, f = 1; char ch;
 41         for(ch = getchar(); !isdigit(ch); ch = getchar())
 42             if(ch == '-') f = -1;
 43         for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
 44         return x * f;
 45     }
 46 
 47     unsigned inpu()
 48     {
 49         unsigned x = 0; char ch;
 50         for(ch = getchar(); !isdigit(ch); ch = getchar());
 51         for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
 52         return x;
 53     }
 54 
 55     ll inp_ll() {
 56         ll x = 0; int f = 1; char ch;
 57         for(ch = getchar(); !isdigit(ch); ch = getchar())
 58             if(ch == '-') f = -1;
 59         for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
 60         return x * f;
 61     }
 62 
 63     char B[25], *outs=B+20, *outr=B+20;
 64     template<class T>
 65     inline void print(register T a,register char x=0){
 66         if(x) *--outs = x, x = 0;
 67 
 68         if(!a)*--outs = '0';
 69         else
 70             while(a)
 71                 *--outs = (a % 10) + 48, a /= 10;
 72 
 73         if(x)
 74             *--outs = x;
 75 
 76         fwrite(outs, outr - outs , 1, stdout);
 77         outs = outr;
 78     }
 79 };
 80 
 81 using io :: print;
 82 using io :: inp;
 83 using io :: inpu;
 84 using io :: inp_ll;
 85 
 86 using i32 = int;
 87 using i64 = long long;
 88 using u8 = unsigned char;
 89 using u32 = unsigned;
 90 using u64 = unsigned long long;
 91 using f64 = double;
 92 using f80 = long double;
 93 
 94 ll power(ll a, ll b, ll p)
 95 {
 96     if (!b) return 1;
 97     ll t = power(a, b/2, p);
 98     t = t*t%p;
 99     if (b&1) t = t*a%p;
100     return t;
101 }
102 
103 ll exgcd(ll a, ll b, ll &x, ll &y)
104 {
105     if (b == 0)
106     {
107         x = 1;
108         y = 0;
109         return a;
110     }
111     ll px, py;
112     ll d = exgcd(b, a%b, px, py);
113     x = py;
114     y = px-a/b*py;
115     return d;
116 }
117 
118 template<class T>
119 inline void freshmin(T &a, const T &b)
120 {
121     if (a > b) a = b;
122 }
123 
124 template<class T>
125 inline void freshmax(T &a, const T &b)
126 {
127     if (a < b) a = b;
128 }
129 
130 const int MAXN = 50010;
131 const int MAXK = 510;
132 const int MOD = 10007;
133 const f80 MI = f80(1)/MOD;
134 const int INF = 100001;
135 
136 int n, k;
137 int S[MAXK][MAXK];
138 
139 vector<int> v[MAXN];
140 int f[MAXN][MAXK], g[MAXN][MAXK];
141 
142 void dfs1(int x, int p)
143 {
144     f[x][0] = 1;
145     for (int i = 1; i <= k; ++ i)
146         f[x][i] = 0;
147     for (auto y : v[x])
148     {
149         if (y == p) continue;
150         dfs1(y, x);
151         (f[x][0] += f[y][0]) %= MOD;
152         for (int i = 1; i <= k; ++ i)
153             (f[x][i] += f[y][i]+f[y][i-1]) %= MOD;
154     }
155 }
156 
157 void dfs2(int x, int p)
158 {
159     if (!p)
160     {
161         for (int i = 0; i <= k; ++ i)
162             g[x][i] = f[x][i];
163     }
164     for (auto y : v[x])
165     {
166         if (y == p) continue;
167         g[y][0] = g[x][0];
168         for (int i = 1; i <= k; ++ i)
169         {
170             int g1 = (g[x][i]-(f[y][i]+f[y][i-1]))%MOD;
171             int g2 = (g[x][i-1]-(f[y][i-1]+(i-2 >= 0 ? f[y][i-2] : 0)))%MOD;
172             g[y][i] = (f[y][i]+g1+g2)%MOD;
173         }
174         dfs2(y, x);
175     }
176 }
177 
178 int main()
179 {
180 
181     S[0][0] = 1;
182     for (int i = 1; i <= 500; ++ i)
183         for (int j = 1; j <= i; ++ j)
184             S[i][j] = (S[i-1][j-1]+S[i-1][j]*j)%MOD;
185 
186     for (int T = inp(); T --; )
187     {
188         n = inp();
189         k = inp();
190         for (int i = 1; i <= n; ++ i)
191             v[i].clear();
192         for (int i = 1; i < n; ++ i)
193         {
194             int x = inp();
195             int y = inp();
196             v[x].push_back(y);
197             v[y].push_back(x);
198         }
199         dfs1(1, 0);
200         dfs2(1, 0);
201         for (int x = 1; x <= n; ++ x)
202         {
203             int ret = 0;
204             int fact = 1;
205             for (int i = 0; i <= k; ++ i)
206             {
207                 (ret += S[k][i]*fact%MOD*g[x][i]) %= MOD;
208                 (fact *= i+1) %= MOD;
209             }
210             printf("%d
", (ret+MOD)%MOD);
211         }
212     }
213 
214     return 0;
215 }

View Code