fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define len(s) (int)s.size()
  5. #define pb push_back
  6. #define eb emplace_back
  7. #define Fi first
  8. #define Se second
  9. #define MASK(x)  ((1LL)<<(x))
  10. #define Bit(x,i) (((x)>>(i))&(1))
  11. #define CountBit(x)  __builtin_popcountll(x)
  12. #define ii pair<int,int>
  13. #define OpenFile(Name) if (fopen(Name".inp","r")) freopen(Name".inp","r",stdin),freopen(Name".out","w",stdout);
  14. using namespace std;
  15.  
  16. int dx[4]={0,1,0,-1};
  17. int dy[4]={1,0,-1,0};
  18.  
  19. template <class C> bool Minimize(C &a, C b) { if (a>b) { a=b; return true; } return false;}
  20. template <class C> bool Maximize(C &a, C b) { if (a<b) { a=b; return true; } return false;}
  21.  
  22. inline ll add(ll a,ll b,ll c) { return (a+b)%c; };
  23. inline ll sub(ll a,ll b,ll c) { return (a-b+c)%c; };
  24. inline ll mul(ll a,ll b,ll c) { return ((a%c)*(b%c))%c; };
  25.  
  26. ll K=1e18,MOD=1e9+7,MOD_base=1777777777;
  27. const int N=1e5+5,M=1e3+3,base=31,BL=447;
  28.  
  29. ///____________________________________________________________________________________________________________________________
  30.  
  31.  
  32. int color[N],tin[N],tout[N],Node[N],cnt=0,dem[N];
  33. vector<int> a[N];
  34. int n;
  35.  
  36. void DFS(int u,int p=-1) {
  37.     tin[u]=++cnt;
  38.     Node[cnt]=u;
  39.  
  40.     for (int v:a[u])
  41.     if (v!=p) DFS(v,u);
  42.  
  43.     tout[u]=cnt;
  44. }
  45.  
  46. int check1(int l,int r) {
  47.     int tmp=0,res=0;
  48.  
  49.     for (int i=l;i<=r;++i) {
  50.         int u=Node[i];
  51.         dem[color[u]]++;
  52.         if (dem[color[u]]>tmp) {
  53.             tmp=dem[color[u]];
  54.             res=color[u];
  55.         }
  56.         //tmp=max(tmp,dem[color[u]]);
  57.     }
  58.  
  59.     for (int i=l;i<=r;++i) dem[color[Node[i]]]=0;
  60.  
  61.     if (tmp>((r-l+1)/2)) return res;
  62.     return -1;
  63. }
  64.  
  65. bool vis[N];
  66.  
  67. int check2(int l,int r) {
  68.     for (int i=l;i<=r;++i) vis[Node[i]]=1;
  69.  
  70.     int tmp=0,res=0,t=0;
  71.  
  72.     for (int i=1;i<=n;++i)
  73.     if (!vis[Node[i]]) {
  74.         int u=Node[i];
  75.         dem[color[u]]++;
  76.         if (dem[color[u]]>tmp) {
  77.             tmp=dem[color[u]];
  78.             res=color[u];
  79.         }
  80.         t++;
  81.         //tmp=max(tmp,dem[color[u]]);
  82.     }
  83.  
  84.     for (int i=l;i<=r;++i) dem[color[Node[i]]]=0;
  85.     for (int i=l;i<=r;++i) vis[Node[i]]=0;
  86.  
  87.     //cout<<"truy van 2: "<<(r-l+1)/2<<' '<<tmp<<'\n';
  88.  
  89.     if (tmp>t/2) return res;
  90.     return -1;
  91. }
  92.  
  93. int b[N],d=0;
  94.  
  95. int main() {
  96.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  97.     OpenFile("TQUERY");
  98.  
  99.     int q; cin>>n>>q;
  100.     for (int i=1;i<=n;++i) cin>>color[i];
  101.  
  102.     for (int i=1;i<n;++i) {
  103.         int u,v; cin>>u>>v;
  104.         a[u].eb(v);
  105.         a[v].eb(u);
  106.     }
  107.  
  108.     DFS(1);
  109.  
  110.     //for (int i=1;i<=n;++i) cout<<i<<' '; cout<<'\n';
  111.     //for (int i=1;i<=n;++i) cout<<Node[i]<<' '; cout<<'\n';
  112.     //for (int i=1;i<=n;++i) cout<<tin[i]<<' '; cout<<'\n';
  113.     //for (int i=1;i<=n;++i) cout<<tout[i]<<' '; cout<<'\n';
  114.  
  115.  
  116.     while (q--) {
  117.         int op,u; cin>>op>>u;
  118.  
  119.         //cout<<op<<' '<<u<<'\n';
  120.         if (op==1) {
  121.             int k=check1(tin[u],tout[u]);
  122.             cout<<k<<'\n';
  123.         } else
  124.         if (op==2) {
  125.             int k=check2(tin[u],tout[u]);
  126.             cout<<k<<'\n';
  127.         } else
  128.         if (op==3) {
  129.             int v; cin>>v;
  130.             cout<<-1<<'\n';
  131.         }
  132.     }
  133.  
  134.  
  135.  
  136.     cerr<<"\nBien dich thanh cong\nTime: "<<(1.0*clock()/CLOCKS_PER_SEC)<<" s\n";
  137.     return 0;
  138. }
  139.  
Success #stdin #stdout #stderr 0.01s 6060KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Bien dich thanh cong
Time: 0.004913 s
https://ideone.com/vlZ3La
language:
C++14 (clang 8.0)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!