PROBLEM LINK:
Author and Editorialist: Ritesh Gupta
Tester: Данило Мочернюк
DIFFICULTY:
Medium-Hard
PREREQUISITES:
DSU, DSU on Trees, Binary Search, DFS
PROBLEM:
You are given a tree T with N nodes (numbered 1 to N). Each node i consists of two positive integers A_i and B_i associated with itself.
We perform this operation exactly once every day for N days. On i-th day, we perform the operation on node P_i. (P is a given permutation of numbers from 1 to N).
An operation on node p is defined as:
- Subtract A_p from all B_q such that q is reachable from p.
- Delete node p and the edges associated with it.
For each node i from 1 to N, you have to print the first day when B_i becomes \le zero or print -1 if it never becomes \le zero.
QUICK EXPLANATION:
- Simply doing what the problem statement suggests in a brute force manner is enough to pass the subtask 1 but the time limit will exceed for the subtask 2.
- To pass subtask 2, we’ll have to rearrange the tree (Tree Decomposition?).
- It can be observed that when an operation is performed on a node (say x), only some particular nodes are affected (the nodes which are reachable from x on that particular day) and the node x is never visited again.
- So, the tree must be decomposed in such a way that in the newly formed tree, any node’s subtree will contain only the nodes that are going to be affected when the operation is performed on the subtree’s root.
- The tree can be built in the bottom to top fashion (sounds like DSU?)
- Once the new tree is formed, DFS can be performed from the root. For each of the children nodes in the root’s subtree, answers can be found using binary search.
EXPLANATION:
Subtask 1:
Consider the nodes in the permutation P in the given order. For each node in P, perform DFS from it assuming it to be the root and subtract A_root from B_j for each j in the root’s component, i.e., j is reachable from the root. If for any j the value B_j value becomes non-positive, the current day would be the answer for that particular node, i.e., node j. Then remove all the edges that connect the root to other nodes. At the end of N days, if there’s some j such that B_j value is still positive, then the answer to node j is -1.
Subtask 2:
Why decompose the given tree?
In the given tree, the operation performed on a particular node affects a specific set of nodes. But it’s hard to maintain the affected nodes and the tree structure in/after each operation. So why not decompose the given tree in a way that if i < j, then P_i will be an ancestor of P_j, such that in the decomposed tree, the below lemmas are satisfied :
Lemma 1: An operation on a node (say x) in the given tree is equivalent to an operation on node x in the decomposed tree such that it affects only the subtree of x (including x itself)
Proof: In the decomposed tree, the operation is performed on the root of any subtree before the operation is performed on the children of that subtree’s root because the tree is decomposed in a way that if i < j, then P_i will be an ancestor of P_j.
Lemma 2: A node x in the decomposed tree is affected only by the ancestors of x i.e., the nodes on the path from the root to x, excluding x
Proof: From Lemma 1, it can be inferred that the operation is performed on a node only if the operation has already been performed on all the ancestors of x i.e., the nodes on the path from the root to x, excluding x.
Let’s denote given tree as OT and the decomposed tree as NT. Construct the new tree, NT with the help of DSU and the knowledge about OT. How?
Start from the node on which the operation will be performed on N-th day, and construct the tree NT in the bottom to the top manner (if i < j, then P_i will be an ancestor of P_j). In other words, for i-th day from N to 1 (decreasing order), including the P_i into the NT, and add edges from P_i to those neighbours of P_i (use OT to get this information) who have already been included in NT. Simply, in NT, connect P_i with the root of each component in which P_i ’s neighbour is present.
- How to decide who will be the root of the component?
- The latest added node will always become the root of the component since the operation on this node will affect all its children. This is easy to maintain and process with DSU.
Now that the NT has been constructed, how to calculate the answer for each node?
Perform a DFS from the root of NT keeping track of the A_i values of nodes in the path from the root to the current node (say x), including x (Hint: use backtracking). Now, extending the Lemma 2, it can be said that if the sum of first k (k being minimum possible) values of A_i on the path from the root to x is greater than or equal to the B_x, then the answer to node x is the day on which the operation was performed on the k-th node on the path from the root to x. If all the values of A_i from root to x sum up to less than B_x, then the answer to node x is -1 because it is not possible for B_x to ever become less than or equal to zero.
Instead of summing up all values of A_i from root to x for each node which may take up O(n) time in the worst case, we can keep a prefix sum array where we can binary search for the B_x value, the time complexity for which will be O(log N) in the worst case.
TIME COMPLEXITY:
TIME: O(NlogN)
SPACE: O(N)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
// #pragma comment(linker, "/STACK: 2000000")
#define int long long
using namespace std;
const int N = 200010;
int par[N], sz[N];
int parent[N], cache[N];
vector <int> v[N], v1[N];
int A[N], B[N];
int ans[N], day[N];
vector <int> prefix_value, prefix_day;
char input[] = "input/input18.txt";
char output[] = "output/output18.txt";
int getPar(int u)
{
while(u != par[u])
{
par[u] = par[par[u]];
u = par[u];
}
return u;
}
void unite(int u, int v)
{
int par1 = getPar(u), par2 = getPar(v);
if(par1 == par2)
return;
parent[cache[par2]] = u;
if(sz[par1] > sz[par2])
{
sz[par1] += sz[par2];
sz[par2] = 0;
par[par2] = par1;
cache[par1] = u;
}
else
{
sz[par2] += sz[par1];
sz[par1] = 0;
par[par1] = par2;
cache[par2] = u;
}
}
void dfs(int curr, int par)
{
// cout << curr << endl;
prefix_value.push_back(prefix_value.back()+A[curr]);
prefix_day.push_back(day[curr]);
if(prefix_value.back() >= B[curr])
{
int idx = lower_bound(prefix_value.begin(), prefix_value.end(), B[curr]) - prefix_value.begin();
// cout << idx << " " << prefix_value.size() << " " << prefix_day.size() << endl;
ans[curr] = prefix_day[idx];
}
for(int i:v1[curr])
{
if(i != par)
{
dfs(i, curr);
}
}
prefix_value.pop_back();
prefix_day.pop_back();
}
int32_t main()
{
// freopen(input, "r", stdin);
// freopen(output, "w", stdout);
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
prefix_day.clear();
prefix_value.clear();
prefix_value.push_back(0);
prefix_day.push_back(0);
for(int i=0;i<=n;i++)
{
v[i].clear();
v1[i].clear();
par[i] = -1;
sz[i] = 0;
parent[i] = -1;
ans[i] = -1;
cache[i] = i;
}
for(int i=1;i<n;i++)
{
int x,y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
vector <int> temp;
for(int i=0;i<n;i++)
{
int x;
cin >> x;
temp.push_back(x);
day[x] = i+1;
}
for(int i=1;i<=n;i++)
{
cin >> A[i];
}
for(int i=1;i<=n;i++)
{
cin >> B[i];
}
reverse(temp.begin(), temp.end());
for(int i=0;i<n;i++)
{
par[temp[i]] = temp[i];
sz[temp[i]] = 1;
parent[temp[i]] = temp[i];
for(int j:v[temp[i]])
{
if(par[j] != -1)
{
unite(temp[i], j);
}
}
// for(int i=1;i<=n;i++)
// cout << parent[i] << " ";
// cout << endl;
}
int root = -1;
for(int i=1;i<=n;i++)
{
if(parent[i] == i)
{
root = i;
continue;
}
v1[i].push_back(parent[i]);
v1[parent[i]].push_back(i);
}
int cnt = 0;
for(int i=1;i<=n;i++)
{
if(parent[i] == i)
cnt++;
}
dfs(root, -1);
for(int i=1;i<=n;i++)
{
cout << ans[i] << " ";
}
cout << endl;
}
}
Tester's Solution
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(a) (int)(a.size())
using namespace std;
const int MAX = 200005;
vector<int> g[MAX] , t[MAX];
int P[MAX] , A[MAX], B[MAX], present[MAX], p[MAX], pos[MAX], answer[MAX];
int find(int u)
{
return p[u] = (p[u] == u ? u : find(p[u]));
}
void unite(int u, int v)
{
v = find(v);
p[v] = u;
t[u].pb(v);
}
vector<ll> path;
vector<int> path2;
void dfs(int u)
{
path.pb(sz(path) ? path.back() + A[u] : A[u]);
path2.pb(pos[u]);
int T = lower_bound(path.begin(), path.end(), B[u]) - path.begin();
answer[u] = T == sz(path) ? -2 : path2[T];
for(auto v : t[u])
dfs(v);
path.pop_back();
path2.pop_back();
}
int main(){
ios::sync_with_stdio(false);
int T;
cin >> T;
while(T--)
{
int N;
cin >> N;
for(int i = 0; i < N; i++)
p[i] = i;
for(int i = 1; i < N; i++)
{
int u , v;
cin >> u >> v;
u--;v--;
g[u].pb(v);
g[v].pb(u);
}
for(int i = 0; i < N; i++)
cin >> P[i];
for(int i = 0; i < N; i++)
cin >> A[i];
for(int i = 0; i < N; i++)
cin >> B[i];
for(int i = N - 1; i >= 0; i--)
{
P[i]--;
pos[P[i]] = i;
for(auto j : g[P[i]])
if(present[j])
unite(P[i] , j);
present[P[i]] = 1;
}
dfs(P[0]);
for(int i = 0; i < N; i++)
{
cout << answer[i] + 1 << " ";
g[i].clear(); t[i].clear();
present[i] = 0;
}
cout << endl;
}
return 0;
}