Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:96777216")
- #include<bits/stdc++.h>
- using namespace std;
- #define INF 1000000009
- #define MAXI(a,b) ((a)>(b)?(a):(b))
- #define MINI(a,b) ((a)<(b)?(a):(b))
- #define MAXN 100006
- int LChild[MAXN], RChild[MAXN], arr[MAXN], add[MAXN];
- void twopoint(int node)
- {
- if (vis[node]) return;
- int par,inpoint = node;
- deque < int > mn,mx;
- /// path er minimum ar maximum track kortesi =>
- mn.push_back(node), mx.push_back(node);
- add[inpoint] = 0;
- while (!vis[inpoint])
- {
- // cout<<arr[inpoint]<<"**"<<endl;
- while(node != 1)
- {
- //printf("*%d ", node);
- par = Parent[node];
- if (LChild[par] == node)
- {
- if(arr [mx.front()]<arr[par]);
- else break;
- }
- else
- {
- if(arr [mn.front()]>arr[par]);
- else break;
- }
- while( mx.size() && mx.back()<arr[ par ] )mx.pop_back();
- mx.push_back( par );
- while( mn.size() && mn.back()>arr[ par ] )mn.pop_back();
- mn.push_back( par );
- node=par;
- }
- ;
- //printf("%d -> %d\n", arr[inpoint], arr[node]);
- // update( node,inpoint,+1 );
- if( inpoint==node )break;
- vis[inpoint] = true;
- inpoint = Parent[inpoint];
- if( mn.front()==inpoint )mn.pop_front();
- if( mx.front()==inpoint )mx.pop_front();
- //
- }
- }
- void sim(int N)
- {
- int node;
- memset(vis, false, sizeof(vis));
- // update(1,1,1);
- vis[1] = true;
- while (!S.empty())
- {
- node = S.top();
- S.pop();
- if (vis[node]) continue;
- twopoint(node);//while(1);
- }
- }
- int main()
- {
- //freopen("data.txt", "r", stdin);
- int T,N,Q,x,y,v,i;
- scanf("%d", &T);
- while (T--)
- {
- scanf("%d", &N);
- init(N);
- for (i=1; i<=N; ++i)
- {
- scanf("%d %d %d", &LChild[i], &RChild[i], &arr[i]);
- if (LChild[i]) Edges[i].push_back(LChild[i]), Parent[LChild[i]] = i;
- if (RChild[i]) Edges[i].push_back(RChild[i]), Parent[RChild[i]] = i;
- }
- // prep(N);
- //print(N);
- sim(N);
- //vis[1] = true; twopoint(3);
- // printf("%d\n", findans());
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement