PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Hemanth Ram
Tester: Anay Karnik
Editorialist: Mohan Abhyas
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
None
PROBLEM:
Bugs Bunny is very smart, but he keeps constantly worrying about the future and is always anxious. Therefore, he keeps hopping between towns without standing still.
The place where Bugs Bunny lives has N towns (numbered 1 through N) with one-way roads connecting them in such a way that they form an arborescence (a tree with all paths directed from the root), rooted at town 1. Therefore, each town except the root has exactly one incoming road; for each i (1 \le i \le N-1), there is a road from town P_i to town i+1. Each town has a distinct rating associated with it; for each valid i, the i-th town has rating A_i.
From a town i, Bugs Bunny is allowed to hop to town j (without visiting any other towns in between), if the following conditions are satisfied:
- there is a path between towns i and j, i.e. a path from town i to town j or from town j to town i
- town j has a lower rating than town i, i.e. A_j \lt A_i
This way, Bugs Bunny can visit a sequence of towns by hopping, starting anywhere and stopping whenever he chooses. Clearly, he cannot keep hopping forever, so the number of such sequences is finite.
Tell Bugs Bunny the number of sequences of two or more towns which can be formed by hopping, given that he can start at any town and stop at any town. Since this number can be very large, calculate it modulo 10^9+7.
EXPLANATION:
Number of sequences ending at node i = 1(sequence - {i}) + number of sequences ending in node j such that A_j > A_i and j is in subtree in of i or j is ancestor of i
This can be done in the following way
Find the eulerian tour of the tree. Maintain two fenwick trees on the eulerian tour of tree.
Traverse the nodes of the the tree in the decreasing order of A_i.
In the first fenwick tree maintain number of sequences ending at i at it’s start position of euler tour.
In the second fenwick tree maintain number of sequences ending at i at it’s start position of euler tour, -1*number of sequences ending at i at it’s end position of euler tour
For processing i i.e., finding no of sequences ending at i
number of sequences ending at subtree of i = sum of values stored in first fenwick tree from start, end positions of i.
number of sequences ending at ancestor of i = sum of values stores in second fenwick tree from position 1 to start position of i
Final answer will be sum of values stored in first fenwick tree
TIME COMPLEXITY:
\mathcal{O}(Nlog(N)) per testcase.
SOLUTIONS:
[details = “Setter’s Solution”]
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
const int INF = INT_MAX;
const int M = 1000000007;
class BIT {
vector<int> tree; int N;
public:
BIT(int n) { tree.resize(n+1,0); N = n; }
int query(int x);
void update(int x, int v);
int rangeSum(int l, int r);
};
int BIT::query(int x) {
x += 1;
int su = 0;
while(x>0) {
su = (su+tree[x])%M;
x -= (x&(-x));
} return su;
}
void BIT::update(int x, int v) {
x += 1;
while(x<=N) {
tree[x] = ((tree[x]+v)%M + M)%M;
x += (x&(-x));
}
}
int BIT::rangeSum(int l, int r) {
if(l>r) return 0;
int ls = query(l-1);
int rs = query(r);
return (rs-ls+M)%M;
}
void eulerTour(int u, vector<vector<int>> &g, vector<int> &tour, vector<int> &start, vector<int> &end, int &x) {
tour.push_back(u);
start[u] = tour.size()-1;
for(auto v:g[u]) {
eulerTour(v, g, tour, start, end, x);
} tour.push_back(u);
end[u] = tour.size()-1;
}
void solve(int tc) {
int n,x=0; cin>>n;
vector<int> parent(n+1,0), a(n+1);
vector<pair<int,int>> a_ix(1);
vector<vector<int>> g(n+1, vector<int>());
for(int i = 2; i<=n; ++i) {
cin>>parent[i];
g[parent[i]].push_back(i);
}
for(int i = 1; i<=n; ++i) {
cin>>a[i];
a_ix.push_back(make_pair(a[i], i));
}
sort(a_ix.begin(), a_ix.end(), greater<pair<int,int>>());
vector<int> tour, st(n+1), en(n+1), ans(n+1);
eulerTour(1, g, tour, st, en, x);
BIT dp_subtrees(2*n), dp_tree(2*n);
for(int i = 0; i<n; ++i) {
int ix = a_ix[i].second;
int cur = 1;
cur = (cur+dp_tree.rangeSum(st[ix], en[ix]))%M;
cur = (cur+dp_subtrees.query(st[ix]))%M;
ans[ix] = cur;
dp_subtrees.update(st[ix], cur);
dp_subtrees.update(en[ix], -cur);
dp_tree.update(st[ix], cur);
}
int tot = 0;
for(int i = 1; i<=n; ++i) tot = (tot+ans[i])%M;
cout<<(tot-n+M)%M<<'\n';
}
int main(){
fastio;
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int t = 1, u = 1;
cin>>t;
while(t--)
solve(u++);
return(0);
}
