Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Forget the shaking animation for a second. From a vertex , where can an apple eventually fall? It can only keep moving downward, never upward.
The final falling vertex must be a leaf in the rooted tree. So for each vertex , you only care about how many leaves exist inside the subtree of .
Define as the number of possible falling vertices for an apple starting at . If has no children, then .
For an internal vertex, the apple chooses one child and then behaves independently inside that child's subtree, so:
After one DFS from root computes all , every query is just:
Use long long, because this can be around . Yes, the whole problem is basically “count leaves in subtrees.” Sneaky little tree gremlin.
An apple starting at vertex always moves from a vertex to one of its children. So it can never leave the subtree of , and it must eventually stop at some vertex with no children — a leaf of the rooted tree.
Therefore, the set of possible vertices from which the apple falls is exactly:
So the only useful value for each vertex is:
Root the tree at vertex . For every vertex :
This is a standard bottom-up tree DP. One DFS is enough.
Because can be , a recursive DFS can be a stack-overflow casino. We avoid that nonsense by building a DFS order iteratively, then processing it in reverse.
For a query :
Thus the answer is simply:
Even if , the apples are still considered separately, so the multiplication is still correct.
For each test case:
Total complexity over all test cases:
Memory usage:
Use long long for answers, since can be as large as .
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> parent(n + 1, 0), order;
order.reserve(n);
vector<int> st;
st.push_back(1);
parent[1] = -1;
while (!st.empty()) {
int u = st.back();
st.pop_back();
order.push_back(u);
for (int v : g[u]) {
if (v == parent[u]) continue;
parent[v] = u;
st.push_back(v);
}
}
vector<ll> dp(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
int u = order[i];
bool leaf = true;
for (int v : g[u]) {
if (v == parent[u]) continue;
leaf = false;
dp[u] += dp[v];
}
if (leaf) dp[u] = 1;
}
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
cout << dp[x] * dp[y] << '\n';
}
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> parent(n + 1, 0), order;
order.reserve(n);
vector<int> st;
st.push_back(1);
parent[1] = -1;
while (!st.empty()) {
int u = st.back();
st.pop_back();
order.push_back(u);
for (int v : g[u]) {
if (v == parent[u]) continue;
parent[v] = u;
st.push_back(v);
}
}
vector<ll> dp(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
int u = order[i];
bool leaf = true;
for (int v : g[u]) {
if (v == parent[u]) continue;
leaf = false;
dp[u] += dp[v];
}
if (leaf) dp[u] = 1;
}
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
cout << dp[x] * dp[y] << '\n';
}
}
return 0;
}