NC15878. Mr. Qiang and His Motorcycles
描述
It’s universally acknowledged that there’re innumerable trees in the campus of HUST.
As is known, Guangtou Qiang earns his living by cutting trees. One day he found a giant tree in a big forest jungle in No.1037, LuoYu Rd. As he has no car for transportation, he decides to cooperate with the evil Wood Hurting Union(WHU), which possesses several types of motorcycles. Each motorcycle can transport a tree whose weight is no larger than wi. Since the value may be less than the total weight of this tree, he will cut some branches of the tree to satisfy the limits. Still, Mr. Qiang wants to earn as much as possible, he wishes to keep the weight of the cut tree to exactly wi. Now Mr. Guang wants to pick up one motorcycle. Can you tell him for each motorcycle how many ways he can to cut a tree satisfying all the requirements?
For simplicity, you may assume this tree to be an unrooted weighted tree in Graph Theory. Each node has a value vi and the total weight of the tree is ∑vi . You can delete some vertices and all edges linked to it, but the remaining graph should still be connected.
输入描述
The first line consists of an integer n(1≤n≤3000), denoting the size of the tree.
Next line contains n integers vi (0≤vi≤2000), denoting the weight of i-th node.
The next n-1 lines contain two integers u and v, representing an edge connecting node u and node v. Nodes are numbered from 1 to n. It is guaranteed that the resulting graph is a connected tree.
Next line is a integer q(1≤q≤10), the number of Mr Qiang's motorcycles.
The next q lines contain only an integer wi (0≤wi≤2000). Each represents the admitted weight of Mr. Qiang's i-th motorcycle.
输出描述
For each of WHU's motorcycle, you should output the number of ways to cut a tree to its admitted weight. Since the answer may be very large, you need to output the answer modulo 998244353. (998244353 is a prime number)
示例1
输入:
6 3 1 2 1 2 2 3 6 2 5 1 3 4 2 2 1 4 4 5 6 7
输出:
3 2 2 3
C++14(g++5.4) 解法, 执行用时: 387ms, 内存消耗: 24296K, 提交时间: 2019-02-03 16:30:35
#include <bits/stdc++.h>
using namespace std;
bool Dbg;
typedef double lf; typedef long long ll; typedef long double llf; typedef vector<int> vint; typedef unsigned int uint; typedef pair<int, int> pii; typedef unsigned long long ull;
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define mid ((l+r)>>1)
#define all(x) x.begin(), x.end()
#define debug(...) (Dbg ? void(fprintf(stderr, __VA_ARGS__)) : void())
#if __cplusplus <= 201103L
#define lop0(i,b) for (register int i = 0, i##end = (b); i < i##end; ++i)
#define lop1(i,b) for (register int i = 1, i##end = (b); i <= i##end; ++i)
#define dlop(i,a,b) for (register int i = (a), i##end = (b); i >= i##end; --i)
#define lop(i,a,b) for (register int i = (a), i##end = (b); i <= i##end; ++i)
#define dlop0(i,b) for (register int i = (b)-1; i >= 0; --i)
#define dlop1(i,b) for (register int i = (b); i >= 1; --i)
#else
#define lop0(i,b) for (int i = 0, i##end = (b); i < i##end; ++i)
#define lop1(i,b) for (int i = 1, i##end = (b); i <= i##end; ++i)
#define dlop(i,a,b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define lop(i,a,b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define dlop0(i,b) for (int i = (b)-1; i >= 0; --i)
#define dlop1(i,b) for (int i = (b); i >= 1; --i)
#endif
#if __cplusplus >= 201103L
mt19937 Rand(time(0) ^ (ull)(new char));
#define mt make_tuple
#else
uint Rand() {static uint x = time(0) ^ (ull)(new char); x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x;}
#endif
#define Debug(x) (Dbg ? void(cerr << #x << " = " << x << '\n') : void())
#define trav(it, a) for (__typeof((a).end())it = (a).begin(); it != (a).end(); ++it)
#define dtrav(it, a) for (__typeof((a).rend())it = (a).rbegin(); it != (a).rend(); ++it)
#define trav1(it, a) for (__typeof((a).end())it = (a).begin(), it##1; it != (a).end(); it = it1)
#define dtrav1(it, a) for (__typeof((a).rend())it = (a).rbegin(), it##1; it != (a).rend(); it = it1)
#define IS(x) (x == 10 || x == 13 || x == ' ')
#define OP operator
#define RT return *this
#define RX x=0;t=P();while((t<'0'||t>'9')&&t!='-')t=P();f=1;\
if(t=='-')t=P(),f=-1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define RU x=0;t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define TR *this,x;return x
#define WI if(x){if(x<0)P('-'),x=-x;c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
#define WU if(x){c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
struct Cg {inline int operator()() {return getchar(); } }; struct Cp {inline void operator()(int x) {putchar(x); } };
struct Fr {
int f, t; Cg P;
#ifdef __SIZEOF_INT128__
inline Fr&OP, (__int128 &x) {RX; x *= f; RT; }
#endif
inline Fr&OP, (int &x) {RX; x *= f; RT; } inline Fr&OP, (ll &x) {RX; x *= f; RT; } inline Fr&OP, (char &x) {for (x = P(); IS(x); x = P()); RT; } inline Fr&OP, (string &x) {cin >> x; RT; } inline Fr&OP, (char *x) {char t = P(); for (; IS(t); t = P()); if (~t) {for (; !IS(t) && ~t; t = P()) * x++ = t; }*x++ = 0; RT; } inline Fr&OP, (lf &x) {scanf("%lf", &x); RT; } inline Fr&OP, (llf &x) {lf y; scanf("%lf", &y); x = y; RT; } inline Fr&OP, (uint &x) {RU; RT; } inline Fr&OP, (ull &x) {RU; RT; }
} in;
struct Fw {
int c, s[50]; Cp P;
#ifdef __SIZEOF_INT128__
inline Fw&OP, (__int128 x) {WI; RT; }
#endif
inline Fw&OP, (int x) {WI; RT; } inline Fw&OP, (uint x) {WU; RT; } inline Fw&OP, (ll x) {WI; RT; } inline Fw&OP, (ull x) {WU; RT; } inline Fw&OP, (char x) {P(x); RT; } inline Fw&OP, (lf x) {printf("%.5f", x); RT; } inline Fw&OP, (const llf &x) {printf("%.5f", lf(x)); RT; } inline Fw&OP, (const string &x) {cout << x; RT; } inline Fw&OP, (const char *x) {while (*x)P(*x++); RT; }
} out;
const int mod = 998244353, inft = 1e9 + 7; const ll infl = llf(1e18) + 1;
const lf eps = 1e-7;
template<typename T> inline T sqr(T x) {return x * x; }
template<typename A, typename B> inline A _gcd(A a, B b) {A t; if (a < b) swap(a, b); if (!b) return a; while (t = a % b) a = b, b = t; return b; }
template<typename A, typename B> inline ll _lcm(A a, B b) {return a / gcd(a, b) * 1ll * b; } template<typename T> inline T abs(T x) {return x >= 0 ? x : -x; }
template<typename A, typename B> inline ll mul(A a, B b, ll mod) {if (b < 0) b = -b, a = -a; ll ret; for (ret = 0; b; b >>= 1) {if (b & 1) ret = (ret + a) % mod; a = (a + a) % mod;} return ret % mod; }
template<typename A, typename B> inline A Pow1(A a, B b, int mod) {A ret; for (ret = 1; b; b >>= 1) {if (b & 1) ret = ret * 1ll * a % mod; a = a * 1ll * a % mod; } return ret % mod; }
template<typename A, typename B> inline ll Pow(A a, B b, ll mod) {assert(b >= 0); a %= mod; if (mod <= 2e9) return Pow1(a, b, mod); ll ret; for (ret = 1; b; b >>= 1) {if (b & 1) ret = mul(ret, a, mod); a = mul(a, a, mod); } return ret % mod; }
template<typename A, typename B> inline A max(A a, B b) {return a > b ? a : b; } template<typename A, typename B> inline A min(A a, B b) {return a < b ? a : b; } template<typename A, typename B> inline void chmax(A &x, B y) {if (x < y) x = y; } template<typename A, typename B> inline void chmin(A &x, B y) {if (x > y) x = y; } template<typename A, typename B> inline void amod(A &x, B y, int mod) {x += y; while (x < 0) x += mod; while (x > mod) x -= mod; } template<typename A> inline void Mod(A &x, int mod) {while (x < 0) x += mod; while (x > mod) x -= mod; }
struct Moder {
int a;
Moder(int a) : a(a) {}
Moder() {}
inline int inv() {return Pow(a, mod - 2, mod);}
inline void operator += (const int b) {a += b; if (a < 0) a += mod; else if (a >= mod) a -= mod;}
inline void operator -= (const int b) {a -= b; if (a < 0) a += mod; else if (a >= mod) a -= mod;}
inline void operator *= (const int b) {a = a * 1ll * b % mod; if (a < 0) a += mod;}
inline void operator /= (const int b) {a = a * 1ll * Pow(b, mod - 2, mod) % mod; if (a < 0) a += mod;}
inline void operator += (ll b) {b %= mod; a += b; if (a < 0) a += mod; else if (a >= mod) a -= mod;}
inline void operator -= (ll b) {b %= mod; a -= b; if (a < 0) a += mod; else if (a >= mod) a -= mod;}
inline void operator *= (ll b) {b %= mod; a = a * 1ll * b % mod; if (a < 0) a += mod;}
inline void operator /= (ll b) {b %= mod; a = a * 1ll * Pow(b, mod - 2, mod) % mod; if (a < 0) a += mod;}
inline void operator += (const Moder &rhs) {*this += rhs.a;}
inline void operator -= (const Moder &rhs) {*this -= rhs.a;}
inline void operator *= (const Moder &rhs) {*this *= rhs.a;}
inline void operator /= (const Moder &rhs) {*this /= rhs.a;}
inline Moder operator + (const Moder &rhs) const {Moder c = *this; c += rhs; return c;}
inline Moder operator - (const Moder &rhs) const {Moder c = *this; c -= rhs; return c;}
inline Moder operator * (const Moder &rhs) const {Moder c = *this; c *= rhs; return c;}
inline Moder operator / (const Moder &rhs) const {Moder c = *this; c /= rhs; return c;}
inline void operator = (const int x) {a = x;}
inline void operator = (const Moder &rhs) {a = rhs.a;}
} dp[3003][2005], ans[2005];
vint G[3003];
int n, siz[3003], a[3003], vis[3003], f[3003], rt, sum;
inline void getrt(int u, int fa) {
siz[u] = 1, f[u] = 0;
for (auto &v : G[u]) {
if (v == fa || vis[v]) continue;
getrt(v, u);
siz[u] += siz[v];
if (siz[v] > f[u]) f[u] = siz[v];
}
if (sum - siz[u] > f[u]) f[u] = sum - siz[u];
if (f[u] < f[rt]) rt = u;
}
inline void dfs(int u, int fa) {
siz[u] = 1;
for (auto &v : G[u])
if (v != fa && !vis[v]) dfs(v, u), siz[u] += siz[v];
}
inline void getans(int u, int fa) {
for (auto &v : G[u])
if (v != fa && !vis[v]) {
lop0(i, 2001) dp[v][i] = (i >= a[v] ? dp[u][i - a[v]] : 0);
getans(v, u);
lop0(i, 2001) dp[u][i] += dp[v][i];
}
}
inline void solve(int u) {
dfs(u, 0); vis[rt] = 1;
lop0(i, 2001) dp[rt][i] = 0;
dp[rt][a[rt]] = 1;
getans(rt, -1);
lop0(i, 2001) ans[i] += dp[rt][i];
for (auto &v : G[rt]) if (!vis[v]) rt = 0, sum = siz[v], getrt(v, 0), solve(v);
}
int main() {
f[0] = inft;
in, n;
sum = n;
lop1(i, n) in, a[i];
lop1(i, n - 1) {
int u, v;
in, u, v;
G[u].pb(v), G[v].pb(u);
}
getrt(1, 0);
solve(rt);
int m; cin >> m;
while (m--) {
int x;
in, x;
out, ans[x].a, '\n';
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 139ms, 内存消耗: 24292K, 提交时间: 2018-05-11 14:32:22
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e3+55;
const int P=998244353;
int num[N],H[N<<1],to[N<<1],V[N],nxt[N<<1],dp[N][2008],size[N],vis[N],mx[N];
int tot,n,root,mi;
void add(int u,int v){
to[++tot]=v;nxt[tot]=H[u];H[u]=tot;
}
void dfssize(int u,int fa){
size[u]=1;
mx[u]=0;
for(int i=H[u];i;i=nxt[i]){
int v=to[i];
if(v==fa||vis[v]) continue;
dfssize(v,u);
size[u]+=size[v];
if(size[v]>mx[u]) mx[u]=size[v];
}
}
void dfsroot(int r,int u,int fa){
if(size[r]-size[u]>mx[u]) mx[u]=size[r]-size[u];
if(mx[u]<mi) mi=mx[u],root=u;
for(int i=H[u];i;i=nxt[i]) {
int v=to[i];
if(v==fa||vis[v]) continue;
dfsroot(r,v,u);
}
}
void calc(int u,int fa){
for(int i=H[u];i;i=nxt[i]){
int v=to[i];
if(v==fa||vis[v]) continue;
for(int i=0;i<=2000;++i) dp[v][i]=((i>=V[v])?dp[u][i-V[v]]:0);
calc(v,u);
for(int i=0;i<=2000;++i) dp[u][i]=(dp[u][i]+dp[v][i])%P;
}
}
void work(int u){
mi=n;
root=u;
dfssize(u,0);
dfsroot(u,u,0);
vis[root]=1;
for(int i=0;i<=2000;++i) dp[root][i]=0;
dp[root][V[root]]=1;
calc(root,0);
for(int i=0;i<=2000;++i) num[i]=(num[i]+dp[root][i])%P;
for(int i=H[root];i;i=nxt[i]){
int v=to[i];
if(vis[v]) continue;
work(v);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",V+i);
int T,x,y;
for(int i=1;i<n;++i) {
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
work(1);
for(scanf("%d",&T);T--;){
scanf("%d",&x);
printf("%d\n",num[x]);
}
}