please someone tell when the editorials for problem of codejunk will come …
meanwhile … can someone share the approach to solve this problem…
I am thankful to every help offered …
please someone tell when the editorials for problem of codejunk will come …
meanwhile … can someone share the approach to solve this problem…
I am thankful to every help offered …
I think I might have an approach. I have not participated in the contest nor implemented it so I am not certain it will work.
The most important observation is that the input graph is a tree. This follows from the fact that the tree is connected and contains one vertex more than the number of edges.
The second observation is that the values A_i don’t matter, only if they are prime or not.
I would first root the tree. Then I would calculate two values for each vertex: min_i and max_i , the minimum/maximum value of prime-composite that can be achieved in the subtree below vertex i. This can be done in \mathcal{O}(n) when considered in leaf-root order. Next I would evaluate the vertices in root-leaf order to update the max and min values to represent the maximum/minimum value for the whole graph. Again this could be done in \mathcal{O}(n). And finally print out ans_i=\max(-min_i,max_i)
thanks for your help… really appretiated it
It can be done by using in-out dp considering first for only primes for computing in-out dp (by making a[i] = 1 for prime and a[i] = -1 for non-prime) and then considering only non-prime for in-out dp(make a[i] = 1 for non-prime and a[i] = -1 for prime).
Where in-dp[u] for a node is the maximum we can gain from all of it’s children(v1, v2, … vn). This can be done by basic dfs by fixing a node as a root.
void dfs (int u, int par) {
in[u] = a[u];
for (int v: g[u]) {
if(v != par) {
dfs(v, u);
in[u] += max(0LL, in[v]);
}
}
}
and out-dp[u] for a node is what we can gain outside the subtree of u. So simply we have to ask the parent. (here in out[u] I am storing max of max(in[u], out[u]))
void dfs2(int u, int par) {
out[u] = in[u];
if(par) {
if(in[u] >= 0) {
out[u] = max(out[u], out[par]);
}
else {
out[u] = max(out[u], in[u] + out[par]);
}
}
for(int v : g[u])
if(v != par)
dfs2(v, u);
}
and final ans node i = max(out1[u], out2[u]);
out1: when considering primes only, out2: considering non-prime only.
vector<bool> prime(N + 1, 1);
void seive(){
prime[0] = prime[1] = 0;
for(int i = 2; i * i <= N; ++i) {
if(prime[i]) {
for(int j = i * i; j <= N;j += i)
prime[j] = 0;
}
}
}
int a[N], in[N], out[N];
vvi g;
int ans[N];
void dfs(int u, int par) {
in[u] = a[u];
for(int v: g[u]) {
if(v != par) {
dfs(v, u);
in[u] += max(0LL, in[v]);
}
}
}
void dfs2(int u, int par) {
out[u] = in[u];
if(par) {
if(in[u] >= 0) {
out[u] = max(out[u], out[par]);
}
else {
out[u] = max(out[u], in[u] + out[par]);
}
}
for(int v : g[u])
if(v != par)
dfs2(v, u);
}
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(0);
seive();
int n;
cin >> n;
g = vvi(n + 1);
for(int i = 1; i <= n; ++i) {
cin >> a[i];
a[i] = 2 * prime[a[i]] - 1;
}
for(int i = 0; i + 1 < n; ++i) {
int u, v;
cin >> u >> v;
g[u].pb(v), g[v].pb(u);
}
dfs(1, 0);
dfs2(1, 0);
for(int i = 1; i <= n; ++i) {
ans[i] = out[i];
}
memset(in, 0, sizeof(in));
memset(out, 0, sizeof(out));
for(int i = 1; i <= n; ++i) {
a[i] = -1.0 * a[i];
}
dfs(1, 0);
dfs2(1, 0);
for(int i = 1; i <= n; ++i) {
cout << max(ans[i], out[i]) << ' ';
}
cout << '\n';
return 0;
}
thanks a lot for your help…