All the tutorials/comments of this question mention to use HLD(Heavy light decomposition) technique or segment tree but why do we require HLD or segment tree for QTREE3(https://www.spoj.com/problems/QTREE3/) question?
There are two types of queries.
1)So I am storing the color of node in a bool array named ‘color’. Thus changing the color of a node is O(1).
2)For second query we can just move from node v to node 1 and update answer if we see a black node. This I believe should be O(logn). Also I need parent pointers for moving up the node which I can precompute by dfs which is O(n).
So overall time complexity is O(n + q*logn) which should have passed the testcases but it is giving me only 66.67/100 marks. Please help.
Code :
#include<cstdio>
#include <iostream>
#include <vector>
#define forn(i,a,b) for(int i = a; i < b; i++)
#define N 100001
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int pa[N]; // Parent pointer
void dfs(vector<int> adj[], bool vis[], int u) // O(n)
{
vis[u] = true;
forn(i,0,adj[u].size())
{
int v = adj[u][i];
if(vis[v] == false)
{
pa[v] = u; // Calculating parent pointers
dfs(adj, vis, v);
}
}
return;
}
int crawlup(vector<int> adj[], bool color[], int n, int v) // O(logn)
{
int ans = -1;
while(v != -1)
{
if(color[v]) ans = v+1;
v = pa[v];
}
return ans;
}
int main()
{
boost;
int n, q;
cin >> n >> q;
bool vis[n];
forn(i,0,n)
{
vis[i] = false;
}
vector<int> adj[n];
bool color[n] = {0};
forn(i,0,n-1)
{
int a, b;
cin >> a >> b;
a--;b--;
adj[a].emplace_back(b);
adj[b].emplace_back(a);
}
pa[0] = -1;
dfs(adj, vis, 0); //O(n)
while(q--)
{
int k;
cin >> k;
if(k == 0) // Query type 1 : O(1)
{
int i;
cin >> i;
i--;
color[i] = !color[i];
}
else //Query type 2 : O(logn)
{
int v;
cin >> v;
v--;
printf("%d\n", crawlup(adj, color, n, v));
}
}
}