You are given a rooted tree with N nodes, labeled 1 through n, rooted at node 1. Each node in the tree can be in one of two colors, black or white, at any point in time. Initially, all nodes are colored black. Over this tree, you need to perform Q queries of the following types:
- 1 u v— report the number of paths in the tree that passes through the edge connecting the nodes u and v, and has both its endpoints colored in black.
- 2 u — flip the color of all the nodes in the subtree of node u, i.e., of all nodes that are in the subtree of node u, color those nodes white which are currently black, and color those nodes black which are currently white.
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(); } }