PROBLEM LINK:
Author: Ayush Ranjan
Tester: Rahul Dugar
Editorialist: Aman Dwivedi
DIFFICULTY:
Medium-Hard
PREREQUISITES:
DFS Tree, Segment Tree with Lazy Propagation
PROBLEM:
You are given two rooted trees T_1 and T_2 consisting of N nodes each, numbered from 1 to N. Any vertex on the path from the root to a vertex v is an ancestor of v.
A vertex numbered w is said to be a common ancestor of a pair (u_1,v_2), if:
- w_1 is an ancestor of u_1 and w_2 is an ancestor of v_2.
- depth_{w_1} = depth_{w_2}, that is, w_1 and w_2 are at equal depths from their respective roots.
Your task is to find the maximum number of ancestors common to a pair of vertices among all such pairs from T_1 and T_2.
QUICK EXPLANATION:
-
Linearize the first tree i.e. T_1 and build a segment tree with nodes in DFS order.
-
Now, run the DFS for the second tree i.e. T_2.
-
If there is a node that matches in depth with its counterpart in the tree T_1, then all nodes in its subtree will count this node as a common ancestor.
-
Hence we increment each node of this subtree as the number of common ancestors for all the nodes of this subtree will increase.
-
At each stage, we find the node which has maximum number of common ancestors.
-
Finally, while leaving the node we undo the increment.
-
-
The maximum number of common ancestor is equal to the the maximum number of common ancestor that any node has at any stage.
EXPLANATION:
For any vertex to be common ancestor, a should be present at the same depth in both of the trees i.e. T_1 and T_2, and there should exists a pair (u_1,v_2) such that vertex is ancestor to both of the nodes in their respective trees.
We will try to explore tree T_2, if we find any node x that matches in depth with its counterpart in tree T_1, then all nodes of its subtree will count this node as an ancestor. It means there can exists a pair as:
where S_{1x} denotes the set of vertex, such that each node of this set is subtree of x for tree T_1 and similarly define S_{2x} for tree T_2.
Also, we can observe that the vertices that were common ancestor before arriving at node x, will not be affected due to tree T_2.
Proof
Let’s say C_1,C_2,.......C_M, be the common ancestors at node y.It means C_1,C_2,.......C_M are the ancestors of node y.
While doing DFS on tree T_2, we can arrive to any node only and only through its parent, it means that all the ancestors of the parent node will also be the ancestors of its child node. So, if we arrived at node x through node y, it means that C_1,C_2,.......C_M are also the ancestors for the node x.
Hence, every time we can choose x from S_{2x} to form a pair, as choosing x results in maximizing the number of common ancestors. Since all the common ancestor are still valid and choosing x gives us one additional vertex as common ancestor i.e. node x itself.
Hence, we can say that our answer completely depends on S_{1x}. i.e. on subtree of node x of tree T_1. It means that the number of common ancestors will be affected due to tree T_1.
Why
Let’s say C_1,C_2,.......C_M, be the common ancestors at node y.It means C_1,C_2,.......C_M are the ancestors of node y.
Since, we are not doing DFS on tree T_2, it means when we arrive at node x, it doesn’t guarantee us that we arrived at this node through its parent. It means that y can be or can’t be the ancestor of node y. Hence, we say that C_1,C_2,.......C_M can be or can’t be the common ancestor for node x.
In order, to do so we will check each time for all nodes of S_{1x}, the number of common ancestor it has and finally find out the maximum number of ancestor any node has in this set.
We can use segment tree for the same, so whenever we encounter a node x that matches in depth with its counterpart in the tree T_1, then we increment all nodes of the subtree x in our segment tree as all the nodes will have one more common ancestor i.e x. During, each update we check for the maximum number of ancestors of any node of the subtree x. Finally when leaving the node, we undo the increment for the all the nodes of subtree x.
If we linearize our Tree T_1 and build the segment tree in the DFS order, then the subtree of any node x will always be continuous. Hence, we can say that we are incrementimg/decrementing in a range.
Hence, we can use Segment Tree with Lazy propagation, as explained here and here and at many places I didn’t link here.
Rest is implementation, which you may refer from solution.
TIME COMPLEXITY:
O(N*log(N)) per testcase
SOLUTIONS:
Setter
/**
>> the_hyp0cr1t3
>> 08.11.2020 13:08:13
**/
#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
template<class T> class Y {
T f;
public:
template<class U> explicit Y(U&& f): f(forward<U>(f)) {}
template<class... Args> decltype(auto) operator()(Args&&... args) {
return f(ref(*this), forward<Args>(args)...);
}
}; template<class T> Y(T) -> Y<T>;
template<class T, class U = int64_t>
struct Segtree {
int N; vector<T> st; vector<U> lazy; vector<bool> pending;
Segtree(int N)
: N(N), st(this->getmx(N)), lazy(st.size()), pending(st.size()) {}
template<class Iter> Segtree(Iter beg, Iter end)
: Segtree(end-beg) { build(1, 1, N, beg, end); }
int getmx(int x) { int y = 1; for(y=1, x<<=1; y<x; y<<=1); return y+2; }
template<class Iter>
void build(int node, int L, int R, Iter beg, Iter end) {
if(L == R) return st[node].set(*beg);
int M = L + R >> 1;
build(node<<1, L, M, beg, beg+(M-L));
build(node<<1|1, M+1, R, beg+(M-L+1), end);
st[node] = T(st[node<<1], st[node<<1|1]);
}
void prop(int node, int L, int R) {
if(L != R) {
pending[node<<1] = pending[node<<1|1] = true;
lazy[node<<1] += lazy[node];
lazy[node<<1|1] += lazy[node];
}
st[node].upd(lazy[node]);
pending[node] = false; lazy[node] = U();
}
T Query(int node, int L, int R, int i, int j) {
if(pending[node]) prop(node, L, R);
if(i > R or j < L) return T();
if(i <= L and j >= R) return st[node];
int M = L + R >> 1;
return T(Query(node<<1, L, M, i, j),
Query(node<<1|1, M+1, R, i, j));
}
void Update(int node, int L, int R, int i, int j, int64_t val) {
if(pending[node]) prop(node, L, R);
if(i > R or j < L) return;
if(i <= L and j >= R) return lazy[node] += val, prop(node, L, R);
int M = L + R >> 1;
Update(node<<1, L, M, i, j, val);
Update(node<<1|1, M+1, R, i, j, val);
st[node] = T(st[node<<1], st[node<<1|1]);
}
auto query(int pos) { return Query(1, 1, N, pos, pos); }
auto query(int l, int r) { return Query(1, 1, N, l, r).val; }
void update(int pos, int64_t val) { Update(1, 1, N, pos, pos, val); }
void update(int l, int r, int64_t val) { Update(1, 1, N, l, r, val); }
};
const int64_t DESPACITO = 2e18;
const int INF = 2e9, MOD = 1e9+7;
const int N = 1e6 + 5;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tc; cin >> tc;
while(tc--) { // O(nlogn)
int i, j, n; array<int, 2> r;
cin >> n;
array<vector<vector<int>>, 2> g;
g[0].resize(n); g[1].resize(n);
for(j = 0; j < 2; j++)
for(i = 0; i < n; i++) {
int p; cin >> p;
if(~p) g[j][--p].pb(i);
else r[j] = i;
}
vector<int> d(n), sub(n, 1), pos(n), tree;
tree.reserve(n);
// dfs down the first tree and tree linearize it to set up for the segment tree
Y([&](auto dfs, int v, int depth) -> void {
d[v] = depth; pos[v] = sz(tree); tree.pb(v);
for(auto& x: g[0][v]) {
dfs(x, depth+1);
sub[v] += sub[x];
}
})(r[0], 0);
// max query, lazy range addition update
struct Node {
int val{0};
Node() = default;
Node(const Node& l, const Node& r)
: val(max(l.val, r.val)) {}
void set(int init) { val = init; }
void upd(int64_t delta) { val += delta; }
}; Segtree<Node> seg(n);
// When exploring a subtree, if the root of the subtree matches in depth
// with its counterpart, then all nodes in its subtree will count this node
// as a special ancestor.
int ans = 0;
Y([&](auto dfs, int v, int depth) -> void {
if(d[v] == depth)
seg.update(pos[v]+1, pos[v]+sub[v], +1);
ans = max(ans, seg.query(1, n));
for(auto& x: g[1][v])
dfs(x, depth+1);
if(d[v] == depth)
seg.update(pos[v]+1, pos[v]+sub[v], -1);
})(r[1], 0);
cout << ans << '\n';
}
} // ~W
Tester
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
int sum_n=0;
vi gra1[1000005],gra2[1000005];
int dep1[1000005],dep2[1000005];
int in[1000005],out[1000005];
int cntr=0;
int answer=0;
int n;
int tr[2000005];
void dfs(int fr, int at, vi gra[], int depth[]) {
in[at]=++cntr;
depth[at]=depth[fr]+1;
for(int i:gra[at])
if(i!=fr)
dfs(at,i,gra,depth);
out[at]=cntr;
}
void update(int l, int r, int v) {
l--;
l+=n,r+=n;
for(; l<r; l>>=1,r>>=1) {
if(l&1) tr[l++]+=v;
if(r&1) tr[--r]+=v;
}
}
int gval(int p) {
int res=0;
p--;
for(p+=n; p>0; p>>=1)
res+=tr[p];
return res;
}
void onelastdfs(int fr, int at) {
if(dep1[at]==dep2[at]) {
update(in[at],out[at],1);
answer=max(answer,gval(in[at]));
}
for(int i:gra1[at])
if(i!=fr)
onelastdfs(at,i);
if(dep1[at]==dep2[at]) {
update(in[at],out[at],-1);
}
}
void solve() {
answer=0;
n=readIntLn(1,1000'000);
sum_n+=n;
assert(sum_n<=1000'000);
fr(i,1,n) {
gra1[i].clear();
gra2[i].clear();
}
int p1=0,p2=0;
fr(i,1,n) {
int te;
if(i!=n)
te=readIntSp(-1,n);
else
te=readIntLn(-1,n);
assert(te);
if(te==-1) {
assert(p1==0);
p1=i;
} else
gra1[te].pb(i);
}
fr(i,1,n) {
int te;
if(i!=n)
te=readIntSp(-1,n);
else
te=readIntLn(-1,n);
assert(te);
if(te==-1) {
assert(p2==0);
p2=i;
} else
gra2[te].pb(i);
}
assert(p1&&p2);
dfs(0,p1,gra1,dep1);
cntr=0;
dfs(0,p2,gra2,dep2);
onelastdfs(p1,p1);
cout<<answer<<endl;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(10);
int t=readIntLn(1,100000);
// int t=1;
// cin>>t;
fr(i,1,t)
solve();
assert(getchar()==EOF);
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
Editorialist
#include<bits/stdc++.h>
using namespace std;
const int mxN=1e6+5;
vector<int> tree1[mxN],tree2[mxN];
int n,timer,ans;
vector<int> in(mxN),out(mxN);
vector<int> depth1(mxN),depth2(mxN);
vector<bool> visited1(mxN),visited2(mxN);
void dfs1(int v){
in[v]=timer++;
visited1[v]=true;
for(auto x: tree1[v]){
if(!visited1[x]){
depth1[x]=depth1[v]+1;
dfs1(x);
}
}
out[v]=timer;
}
void dfs2(int v){
visited2[v]=true;
for(auto x: tree2[v]){
if(!visited2[x]){
depth2[x]=depth2[v]+1;
dfs2(x);
}
}
}
struct Node {
int l,r,val,lazy_add;
Node() : l(), r(), val(), lazy_add() {}
Node(int _l, int _r) : l(_l), r(_r), val(0), lazy_add(0) {}
};
Node tree[4*mxN];
int L;
void build(int n){
L=max(1,n);
while(L&(L-1)) L++;
for(int i=0;i<L;i++)
tree[L+i]=Node(i,i+1);
for(int i=L-1;i>0;i--)
tree[i]=Node(tree[2*i].l,tree[2*i+1].r);
}
void push(int v){
tree[2*v].val+=tree[v].lazy_add;
tree[2*v].lazy_add+=tree[v].lazy_add;
tree[2*v+1].val+=tree[v].lazy_add;
tree[2*v+1].lazy_add+=tree[v].lazy_add;
tree[v].lazy_add = 0;
}
void update(int v,int l,int r,int x){
if(l<=tree[v].l && tree[v].r<=r){
tree[v].val+=x;
tree[v].lazy_add+=x;
return;
}
if(l>=tree[v].r || tree[v].l>=r) return;
push(v);
update(2*v,l,r,x);
update(2*v+1,l,r,x);
tree[v].val=max(tree[2*v].val,tree[2*v+1].val);
}
int query(int v,int l,int r) {
if(l<=tree[v].l && tree[v].r<=r){
return tree[v].val;
}
if(l>=tree[v].r || tree[v].l>=r) return 0;
push(v);
return max(query(2*v,l,r),query(2*v+1,l,r));
}
void final_dfs(int v){
visited2[v]=false;
if(depth1[v]==depth2[v]){
update(1,in[v],out[v],1);
ans=max(ans,query(1,0,n));
}
for(auto x: tree2[v]){
if(visited2[x]){
final_dfs(x);
}
}
if(depth1[v]==depth2[v]){
update(1,in[v],out[v],-1);
}
}
void solve(){
cin>>n;
build(n);
int root1,root2;
for(int i=0;i<n;i++){
tree1[i].clear();
tree2[i].clear();
visited1[i]=false;
visited2[i]=false;
depth1[i]=0;
depth2[i]=0;
}
for(int i=0;i<n;i++){
int x; cin>>x;
if(x==-1) root1=i;
else{
x--;
tree1[x].push_back(i);
tree1[i].push_back(x);
}
}
timer=0;
dfs1(root1);
for(int i=0;i<n;i++){
int x; cin>>x;
if(x==-1) root2=i;
else{
x--;
tree2[x].push_back(i);
tree2[i].push_back(x);
}
}
dfs2(root2);
ans=0;
final_dfs(root2);
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin>>t;
while(t--){
solve();
}
}