Run with input

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,a,b) for(int i = a; i<b ; i++)
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define M 1000000007
int mod(int x){
return ((x%M + M)%M);
}
int add(int a,int b){
return mod(mod(a)+mod(b));
}
int mul(int a,int b){
return mod(mod(a)*mod(b));
}
// ****************************************************************************
const int maxn = 2e5 + 5;
int ft[2*maxn],tree[8*maxn],diary[8*maxn],in[maxn],out[maxn],timer;
vector<int>v[maxn];

void dfs(int src,int par){
ft[timer] = src;
in[src] = timer++;
for(auto &it : v[src]){
if(it==par)
continue;
dfs(it,src);
}
ft[timer] = src;
out[src] = timer++;
}
void build(int treeind,int tl,int tr){
if(tl>tr)
return;
if(tl==tr){
tree[treeind] =1ll;
return;
}
int mid = (tl + tr)/2;
build(2*treeind+1,tl,mid);
build(2*treeind+2,mid+1,tr);
tree[treeind] = tree[2*treeind+1] + tree[2*treeind+2];
}
void prop(int treeind,int tl,int tr){
if(diary[treeind]){
int val = tree[treeind];
tree[treeind] = (tr-tl+1) - val;
if(tl!=tr){
diary[2*treeind+1]^=1ll;
diary[2*treeind+2]^=1ll;
}
diary[treeind] = 0;
}
}
int l,r;
void upd(int treeind,int tl,int tr){
if(tl>tr)
return;
prop(treeind,tl,tr);
if(tl>r || tr<l)
return;
if(tl>=l && tr<=r){
int val = tree[treeind];
tree[treeind] = (tr-tl+1) - val;
if(tl!=tr){
diary[2*treeind+1]^=1ll;
diary[2*treeind+2]^=1ll;
}
return;
}
int mid = (tl + tr)/2;
upd(2*treeind+1,tl,mid);
upd(2*treeind+2,mid+1,tr);
tree[treeind] = tree[2*treeind+1] + tree[2*treeind+2];
}
int qry(int treeind,int tl,int tr){
if(tl>tr)
return 0ll;
prop(treeind,tl,tr);
if(tl>r || tr<l)
return 0ll;
if(tl>=l && tr<=r)
return tree[treeind];
int mid = (tl + tr)/2;
return qry(2*treeind+1,tl,mid) + qry(2*treeind+2,mid+1,tr);
}

void solve(){
int n;
cin>>n;
fo(i,0,n-1){
int a,b;
cin>>a>>b;
v[a].pb(b);
v[b].pb(a);
}
dfs(1,0);
build(0,0,2*n-1);
int q;
cin>>q;
while(q--){
int ty;
cin>>ty;
if(ty==1){
int u,v;
cin>>u>>v;
int par,ch;
if(in[u]>=in[v] && out[u]<=out[v]){
par=v,ch=u;
}
else{
par=u,ch=v;
}
l = in[ch];
r = out[ch];
int tot = tree[0]/2;
int ans = qry(0,0,2*n-1);
ans/=2;
cout<<(tot-ans)*ans<<"\n";
}
else{
int node;
cin>>node;
l = in[node];
r = out[node];
upd(0,0,2*n-1);
}
}
}
signed main()
{
FIO
int t;
t=1;
// cin>>t;
while(t--)
{
solve();
}
}

#include <bits/stdc++.h>
#define int long long int
#define endl '\n'
using namespace std;
signed main()
{

int t;cin>>t;
while(t--)
{
int n,x,y,i;cin>>n;
string s;
cin>>s;
cin>>x>>y;
int a[n+1],b[n+1];
a[0]=0;b[0]=0;
for(i=0;i<n;i++)
{
if(s[i]=='E')
{
a[i+1]=a[i]+0;
}
else if(s[i]=='W')
{
a[i+1]=min(2ll*x,2ll*y)+a[i];
}
else if(s[i]=='N')
{
a[i+1]=min(x,3ll*y)+a[i];
}
else if(s[i]=='S')
{
a[i+1]=min(y,3ll*x)+a[i];
}
}
for(i=0;i<n;i++)
{
if(s[i]=='E')
{
b[i+1]=b[i]+min(2ll*x,2ll*y);
}
else if(s[i]=='W')
{
b[i+1]=0+b[i];
}
else if(s[i]=='N')
{
b[i+1]=min(y,3ll*x)+b[i];
}
else if(s[i]=='S')
{
b[i+1]=min(x,3ll*y)+b[i];
}
}
int ans=min(a[n],b[n]),z;
for(i=1;i<n;i++)
{
z= a[i]+b[n]-b[i];
ans=min(ans,z);
}
cout<<ans<<endl;
}
return 0;
}

Steps:

Create a Node structure that has a left and right pointer to point to the left and right child nodes.

Create a BST using recursion. While insertion the value is checked with the root value. If the value is lesser than the root we move to the left subtree else to the right subtree. This continues until an empty place is found to place the new node.

The display function displays the nodes of the tree in an inorder fashion this is left root right.

The search function returns NULL if no such target is found else returns the node with the target value.

#include<iostream>

using namespace std;

struct Node{
string val;
struct Node *left;
struct Node *right;
};

//method to insert new nodes
struct Node* insertNode(struct Node *root,string val)
{
if(root==NULL)
{
//create a new node
struct Node *newNode=new Node();
newNode->val=val;
newNode->left=newNode->right=NULL;
return newNode;
}

if(val<root->val)
root->left=insertNode(root->left,val);
else
root->right=insertNode(root->right,val);

return root;
}

//method to display the tree
void display(struct Node *root)
{
//perform inorder traversal
if(root!=NULL)
{
display(root->left);
cout<<root->val<<" ";
display(root->right);
}
}

//method to search the tree
struct Node* searchNode(struct Node *root,string val)
{
if(root==NULL || root->val==val)
{
return root;
}
if(root->val<val)
{
return searchNode(root->right,val);
}
return searchNode(root->left,val);
}

int main()
{
struct Node *root=NULL,*node;

//display the menu
int choice;
string val;

while(1)
{
cout<<"1. Insert Node"<<endl;
cout<<"2. Display Nodes"<<endl;
cout<<"3. Search Node"<<endl;
cout<<"4. Exit"<<endl;
cout<<"Enter choice: ";
cin>>choice;

fflush(stdin);
switch(choice)
{
case 1: cout<<"Enter string: ";
getline(cin,val);
root=insertNode(root,val);
cout<<val<<" added"<<endl;
break;
case 2: cout<<"Inorder traversal of tree: ";
display(root);
cout<<endl;
break;
case 3: cout<<"Enter string: ";
getline(cin,val);
node=searchNode(root,val);
if(node==NULL)
{
cout<<val<<" not found."<<endl;
}
else{
cout<<val<<" found."<<endl;
}
break;
case 4: exit(0);
default:cout<<"Wrong choice"<<endl;
}
cout<<endl;
}
}