I’m trying to do RRTREE, and (as usual 
) my code is working on all testcases I can think of but still giving WA. Time is not an issue, it takes only 0.08 seconds to run.
Can someone point out the mistake or give a testcase where my solution fails?
The code is here, also reproduced below:
EDIT : I found one mistake; I was not updating second maximum size; but it still gives WA, meaning I’m doing other mistakes too.
I have added the updated link and code (which still don’t work).
EDIT 2:
I found my mistake: it is 1 + (pos <<1); the brackets are important.
Unfortunately, now I’m getting TLE.
My solution is this. I made my own random testcase generator and checker, and my code runs in < 0.3 seconds for N = 100000. What is going wrong?
My testcase generator:
#include <bits/stdc++.h>
using namespace std;
int main(){
cout << 1 << endl;
srand(time(NULL));
//int N = rand() % 75000;
int N = 100000;
cout << N << endl;
for(int i = 2; i <= N; i++){
cout << (1 + (rand()%(i-1))) << endl;
}
return 0;
}
My new code(giving TLE, almost same):
#include <bits/stdc++.h>
using namespace std;
struct node{
int id;
int depth;
int subtree_sz;
int color; //1 for white, 0 for black
int halfsize;
int maxdistance;
int secondmax;
vector<node*> nodesonpath;
vector<node*> neighbors;
vector<int> upsegtree; //segtree with point update and range query
vector<int> downsegtree;
node* parent;
node* headnode;
node* head_max;
};
node* newNode(int id){
node* n = new node;
n->id = id;
n->parent = n->headnode = NULL;
n->subtree_sz = 1;
n->color = 0;
n->head_max = NULL;
n->maxdistance = -100000;
n->secondmax = -100000;
return n;
}
int global_max;
/*
int reverse(int num, int logn){
int res = 0;
for (int i = 0; i < logn; i++) {
if (num & (1 << i))
res |= 1 << (logn - 1 - i);
}
return res;
}*/
int x,y,z;
void dfs(node* n, node* parent){
if(!parent){
n->depth = 0;
}
else n->depth = parent->depth + 1;
//sets up subtree sizes
n->parent = parent;
n->subtree_sz = 1;
for(int i = 0; i < n->neighbors.size(); i++){
if(n->neighbors[i] == parent) continue;
dfs(n->neighbors[i],n);
n->subtree_sz += n->neighbors[i]->subtree_sz;
}
}
void dfs_hld(node* n, node* parent, node* headnode){
n->headnode = headnode;
headnode->nodesonpath.push_back(n);
for(auto &n1 : n->neighbors){
if(n1 == parent) continue;
if(n1->subtree_sz > (n->subtree_sz - 1)/2){
dfs_hld(n1,n,headnode);
}
else {
dfs_hld(n1,n,n1);
}
}
if(headnode == n){
//if(n->id == 74787) cout << 2 << endl;
x = n->nodesonpath.size();
//smallest power of 2 >= x; assume x fits in 32 bit
x--;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x++;
n->halfsize = x;
n->upsegtree.resize(2*x);
n->downsegtree.resize(2*x);
for(int i = 0; i < 2*x; i++){
n->upsegtree[i] = n->downsegtree[i] = -100000; //maxdistance initially none
}
}
}
/*
void update(vector<int> &segtree, int n, int l, int r, int value){
//l and r are 0 indexed
//n = size of segtree/2
r++;
for(l += n, r += n; l < r; l >>= 1, r >>= 1){
//if(l&1) then l is
if(l & 1) segtree[l++] += value;
if(r & 1) segtree[--r] += value;
}
}*/
void update(vector<int> &segtree, int n, int pos, int value){
//l and r 0 indexed
// n = size of segtree/2
pos += n;
if(segtree[pos] >= value) return;
segtree[pos] = value;
pos >>= 1;
while(pos){
//if(value == 5){cout << pos << endl;
//cout << segtree[pos << 1] << ' ' << segtree[1 + (pos << 1)] << endl;}
segtree[pos] = max(segtree[pos << 1], segtree[1 + (pos << 1)]);
pos >>= 1;
}
}
/*
int query(vector<int> &segtree, int n, int pos){
int cur = 1, direction = reverse(pos, log2(n));
while(cur < n){
segtree[cur << 1] += segtree[cur];
segtree[1 + (cur << 1)] += segtree[cur];
segtree[cur] = 0;
cur <<= 1;
if(direction & 1) cur++;
direction >>= 1;
}
return segtree[cur];
}*/
int query(vector<int> segtree, int n, int l, int r){
int retval = -10000;
r++;
for(l += n, r += n; l < r; l >>= 1, r >>= 1){
if(l & 1) retval = max(retval, segtree[l++]);
if(r & 1) retval = max(retval,segtree[--r]);
}
return retval;
}
vector<node*> nodes;
void addEdge(int a, int b){
nodes[a]->neighbors.push_back(nodes[b]);
nodes[b]->neighbors.push_back(nodes[a]);
}
void updateNode(node* &n, node* curhead, int distance){
//cout << "u " << n->id << " " << distance << endl;
node* head = n->headnode;
if(distance > n->maxdistance){
if(n->head_max == curhead){
n->maxdistance = distance;
}
else{
n->secondmax = n->maxdistance;
n->maxdistance = distance;
n->head_max = curhead;
}
}
else if(distance > n->secondmax){
if(curhead != n->head_max)
n->secondmax = distance;
}
int pos = n->depth - head->depth;
update(head->upsegtree, head->halfsize, pos, distance - n->depth);
update(head->downsegtree, head->halfsize, pos, distance + n->depth);
if(head->parent){
updateNode(head->parent, head, distance + pos + 1);
}
}
int maxinCurrent(node* n, node* headcome){
int retval, temp, pos;
if(n->head_max == headcome) retval = n->secondmax;
else retval = n->maxdistance;
//cout << "----" << endl;
node* head = n->headnode;
pos = n->depth - head->depth;
if(pos){
temp = query(head->upsegtree, head->halfsize, 0, pos - 1);
retval = max(temp + n->depth, retval);
//cout << retval << endl;
}
if(pos < head->nodesonpath.size() - 1){
temp = query(head->downsegtree, head->halfsize, pos + 1, head->nodesonpath.size() - 1);
retval = max(temp - n->depth, retval);
}
return retval;
}
int maxOverall(node* n, node* headcome){
int retval = maxinCurrent(n, headcome), temp;
node* head = n->headnode;
if(head->parent){
temp = maxOverall(head->parent, head);
retval = max(retval, temp + n->depth - head->depth + 1);
}
return retval;
}
void makewhite(node* &n, bool print){
int curmax = maxOverall(n, NULL);
global_max = max(global_max, curmax);
//if(print) cout << max(global_max, 0) << endl;
if(print) printf("%d\n", max(global_max,0));
n->color = 1;
updateNode(n,NULL,0);
}
void solve(){
global_max = -100000;
int N;
//cin >> N;
scanf("%d", &N);
nodes.resize(N);
for(int i = 0; i < N; i++){
nodes[i] = newNode(i);
}
for(int i = 1; i < N; i++){
//cin >> x;
scanf("%d",&x);
addEdge(i, x-1);
}
dfs(nodes[0], NULL);
dfs_hld(nodes[0], NULL, nodes[0]);
makewhite(nodes[0], false);
for(int i = 1; i < N; i++){
makewhite(nodes[i], true);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
//cin >> T;
scanf("%d",&T);
while(T--){
solve();
}
/*
nodes.resize(12);
for(int i = 0; i < 12; i++){
nodes[i] = newNode(i);
}
addEdge(0,1);
addEdge(1,2);
addEdge(2,3);
addEdge(3,4);
addEdge(4,5);
addEdge(2,6);
addEdge(6,7);
addEdge(7,8);
addEdge(0,9);
addEdge(9,10);
addEdge(10,11);
dfs(nodes[0], NULL);
dfs_hld(nodes[0], NULL, nodes[0]);
makewhite(nodes[0]);
cout << maxOverall(nodes[7], NULL) << endl;
makewhite(nodes[8]);
cout << maxOverall(nodes[5], NULL) << endl;
makewhite(nodes[11]);
cout << maxOverall(nodes[5], NULL) << endl;*/
return 0;
}
#include <bits/stdc++.h>
using namespace std;
struct node{
int id;
int depth;
int subtree_sz;
int color; //1 for white, 0 for black
int halfsize;
int maxdistance;
int secondmax;
vector<node*> nodesonpath;
vector<node*> neighbors;
vector<int> upsegtree; //segtree with point update and range query
vector<int> downsegtree;
node* parent;
node* headnode;
node* head_max;
};
node* newNode(int id){
node* n = new node;
n->id = id;
n->parent = n->headnode = NULL;
n->subtree_sz = 1;
n->color = 0;
n->head_max = NULL;
n->maxdistance = -100000;
n->secondmax = -100000;
return n;
}
int global_max;
int x,y,z;
void dfs(node* n, node* parent){
if(!parent){
n->depth = 0;
}
else n->depth = parent->depth + 1;
//sets up subtree sizes
n->parent = parent;
n->subtree_sz = 1;
for(int i = 0; i < n->neighbors.size(); i++){
if(n->neighbors[i] == parent) continue;
dfs(n->neighbors[i],n);
n->subtree_sz += n->neighbors[i]->subtree_sz;
}
}
void dfs_hld(node* n, node* parent, node* headnode){
n->headnode = headnode;
headnode->nodesonpath.push_back(n);
for(auto &n1 : n->neighbors){
if(n1 == parent) continue;
if(n1->subtree_sz > (n->subtree_sz - 1)/2){
dfs_hld(n1,n,headnode);
}
else {
dfs_hld(n1,n,n1);
}
}
if(headnode == n){
//if(n->id == 74787) cout << 2 << endl;
x = n->nodesonpath.size();
//smallest power of 2 >= x; assume x fits in 32 bit
x--;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x++;
n->halfsize = x;
n->upsegtree.resize(2*x);
n->downsegtree.resize(2*x);
for(int i = 0; i < 2*x; i++){
n->upsegtree[i] = n->downsegtree[i] = -100000; //maxdistance initially none
}
}
}
void update(vector<int> &segtree, int n, int pos, int value){
// n = size of segtree/2
pos += n;
if(segtree[pos] >= value) return;
segtree[pos] = value;
pos >>= 1;
while(pos){
segtree[pos] = max(segtree[pos << 1], segtree[1 + pos << 1]);
pos >>= 1;
}
}
int query(vector<int> segtree, int n, int l, int r){
int retval = -10000;
r++;
for(l += n, r += n; l < r; l >>= 1, r >>= 1){
if(l & 1) retval = max(retval, segtree[l++]);
if(r & 1) retval = max(retval,segtree[--r]);
}
return retval;
}
vector<node*> nodes;
void addEdge(int a, int b){
nodes[a]->neighbors.push_back(nodes[b]);
nodes[b]->neighbors.push_back(nodes[a]);
}
void updateNode(node* &n, node* curhead, int distance){
//cout << "u " << n->id << " " << distance << endl;
node* head = n->headnode;
if(distance > n->maxdistance){
if(n->head_max == curhead){
n->maxdistance = distance;
}
else{
n->secondmax = n->maxdistance;
n->maxdistance = distance;
n->head_max = curhead;
}
}
else if(distance > n->secondmax){
if(curhead != n->head_max)
n->secondmax = distance;
}
int pos = n->depth - head->depth;
update(head->upsegtree, head->halfsize, pos, distance - n->depth);
update(head->downsegtree, head->halfsize, pos, distance + n->depth);
if(head->parent){
updateNode(head->parent, head, distance + pos + 1);
}
}
int maxinCurrent(node* n, node* headcome){
int retval, temp, pos;
if(n->head_max == headcome) retval = n->secondmax;
else retval = n->maxdistance;
//cout << "----" << endl;
//cout << n->id << " " << retval << endl;
node* head = n->headnode;
pos = n->depth - head->depth;
if(pos){
temp = query(head->upsegtree, head->halfsize, 0, pos - 1);
retval = max(temp + n->depth, retval);
//cout << retval << endl;
}
if(pos < head->nodesonpath.size() - 1){
temp = query(head->downsegtree, head->halfsize, pos + 1, head->nodesonpath.size() - 1);
retval = max(temp - n->depth, retval);
}
return retval;
}
int maxOverall(node* n, node* headcome){
int retval = maxinCurrent(n, headcome), temp;
//cout << n->id << " " << retval << endl;
node* head = n->headnode;
if(head->parent){
temp = maxOverall(head->parent, head);
retval = max(retval, temp + n->depth - head->depth + 1);
}
return retval;
}
void makewhite(node* &n, bool print){
int curmax = maxOverall(n, NULL);
global_max = max(global_max, curmax);
if(print) cout << max(global_max, 0) << endl;
n->color = 1;
updateNode(n,NULL,0);
}
void solve(){
global_max = -100000;
int N;
cin >> N;
nodes.resize(N);
for(int i = 0; i < N; i++){
nodes[i] = newNode(i);
}
for(int i = 1; i < N; i++){
cin >> x;
addEdge(i, x-1);
}
dfs(nodes[0], NULL);
dfs_hld(nodes[0], NULL, nodes[0]);
makewhite(nodes[0], false);
for(int i = 1; i < N; i++){
makewhite(nodes[i], true);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
while(T--){
solve();
}
/*
nodes.resize(12);
for(int i = 0; i < 12; i++){
nodes[i] = newNode(i);
}
addEdge(0,1);
addEdge(1,2);
addEdge(2,3);
addEdge(3,4);
addEdge(4,5);
addEdge(2,6);
addEdge(6,7);
addEdge(7,8);
addEdge(0,9);
addEdge(9,10);
addEdge(10,11);
dfs(nodes[0], NULL);
dfs_hld(nodes[0], NULL, nodes[0]);
makewhite(nodes[0]);
cout << maxOverall(nodes[7], NULL) << endl;
makewhite(nodes[8]);
cout << maxOverall(nodes[5], NULL) << endl;
makewhite(nodes[11]);
cout << maxOverall(nodes[5], NULL) << endl;*/
return 0;
}
What my code does is roughly the following:
Do a heavy light decomposition of the tree formed at the very end and mark nodes using two colors: black means inactive and white means active.
At any moment maintain two segtrees on the nodes in a path: upsegtree which answers max queries of (\text{(maximum distance from a white node on a "hanging off path" from this node)}- \text{depth of node}), and a downsegtree answering (\text{(maximum distance from a white node on a "hanging off path" from this node)} + \text{depth of node}).
Also maintain the maximum distance of a white node in a hanging off path and the second maximum distance of such a node such that this node is in a different path as the max node.
Whenever I query the max distance from a node, having just walked up from the head of a different chain, \text{head}, I initialize this distance to the max value if its from a different chain from what I came, or else the second max. Now query the upsegtree for \text{head} \cdots \text{parent}(node) and add depth of node to this, and then update max if this is bigger, similar query downsegtree for lower nodes, then subtract depth of this node, and update max. Do this for all chains walking up, recursively. We can perform updates on each chain recursively upwards.
Now one by one mark nodes as active and answer the queries.
Sorry for a long explanation, but it’s kinda difficult to put in words what I was trying to code .
changed the segment tree implementation from vector to int* and got AC in 0.14 seconds.