fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. #define  prec(n)        fixed<<setprecision(n)
  6. #define  optimize       ios::sync_with_stdio(0); cin.tie(0);
  7. #define  PI             acos(-1.0)
  8. #define  RESET(a, b)    memset(a, b, sizeof(a))
  9. #define  pb             push_back
  10. #define  sz(v)          v.size()
  11. #define  pii            pair<int,int>
  12. #define  ff             first
  13. #define  ss             second
  14. #define  vv             vector<int>
  15. #define  all(v)         v.begin(),v.end()
  16.  
  17. int const MAXN=120001;
  18. int const MAXQ=250001;
  19. int const LN=20;
  20. int ID[2*MAXN],st[MAXN],en[MAXN],level[MAXN],a[MAXN];
  21. int dp[MAXN][LN],vis[MAXN];
  22. vv g[MAXN];
  23. int Map[MAXN];
  24. int ANS[MAXN];
  25. int n,q,K,cur;
  26. struct Query{
  27.     int index, L, R,lc,val;
  28.     bool operator < (const Query &other) const {
  29. 		int block_own = L/K;
  30. 		int block_other = other.L/K;
  31. 		if(block_own == block_other)
  32.             return R < other.R;
  33. 		return block_own < block_other;
  34. 	}
  35. }Q[MAXQ];
  36.  
  37. void dfs(int u,int p){
  38.    st[u]= ++cur;
  39.    ID[cur]=u;
  40.    //T[u]=p;
  41.    level[u]=level[p]+1;
  42.    dp[u][0] = p;
  43.     for(int i=1; i<LN; ++i)
  44.         dp[u][i] = dp[dp[u][i-1]][i-1];
  45.    for(int i=0;i<g[u].size();i++){
  46.      int x=g[u][i];
  47.      if(x==p) continue;
  48.      dfs(x,u);
  49.    }
  50.    en[u]= ++cur;
  51.    ID[cur]=u;
  52. }
  53. int lca(int u, int v) {
  54.     if(level[u] < level[v])
  55.         swap(u, v);
  56.     int diff = level[u] - level[v];
  57.     for(int i=0; i<LN; ++i) {
  58.         if((1<<i) & diff)
  59.             u = dp[u][i];
  60.     }
  61.     if(u == v)
  62.         return u;
  63.     for(int i=LN-1; i>=0; --i) {
  64.         if(dp[u][i] != dp[v][i]) {
  65.             u = dp[u][i];
  66.             v = dp[v][i];
  67.         }
  68.     }
  69.     return dp[u][0];
  70. }
  71. void add(int x){
  72.     if(vis[x]==0){
  73.         Map[a[x]]=1;
  74.         vis[x]=1;
  75.     }
  76.     else{
  77.         Map[a[x]]=0;
  78.         vis[x]=0;
  79.     }
  80. }
  81. void mos(){
  82.    for(int i=0;i<q;i++){
  83.       int cl=1,cr=0;
  84.       while(cr<=Q[i].R) add(ID[++cr]);
  85.       while(cl<Q[i].L) add(ID[cl++]);
  86.       while(cr>=Q[i].R) add(ID[cr--]);
  87.       while(cl>Q[i].L) add(ID[--cl]);
  88.       int u= ID[cl],v=ID[cr];
  89.       if(Q[i].lc!=u && Q[i].lc!=v) add(Q[i].lc);
  90.       //cout<<Map[Q[i].val]<<endl;
  91.       if(Map[Q[i].val]==1){
  92.         //cout<<"yes"<<endl;
  93.          ANS[Q[i].index]=1;
  94.       }
  95.       if(Q[i].lc!=u && Q[i].lc!=v) add(Q[i].lc);
  96.    }
  97. }
  98. int main()
  99. {
  100.     while((scanf("%d%d",&n,&q))!=EOF){
  101.         for(int i=1;i<=n;i++){
  102.             scanf("%d",&a[i]);
  103.         }
  104.         for(int i=1;i<=n;i++){
  105.             g[i].clear();
  106.             vis[i]=0;
  107.             Map[i]=0;
  108.             level[i]=0;
  109.         }
  110.         for(int i=0;i<=n;i++){
  111.             for(int j=0;j<=LN;j++) dp[i][j]=0;
  112.         }
  113.         for(int i=1;i<=n-1;i++){
  114.             int x,y;
  115.             scanf("%d%d",&x,&y);
  116.             g[x].pb(y);
  117.             g[y].pb(x);
  118.         }
  119.         cur=0;
  120.         dfs(1,-1);
  121.         //for(int i=1;i<=10;i++) cout<<ID[i]<<" ";
  122.         for(int i=0;i<q;i++){
  123.             int x,y,v1;
  124.             scanf("%d%d%d",&x,&y,&v1);
  125.             Q[i].index=i;
  126.             Q[i].val=v1;
  127.             Q[i].lc=lca(x,y);
  128.             //cout<<Q[i].lc<<endl;
  129.             if(st[x]>st[y]) swap(x,y);
  130.             if(Q[i].lc==x){
  131.                 Q[i].L=st[x];
  132.                 Q[i].R=st[y];
  133.             }
  134.             else{
  135.                 Q[i].L=en[x];
  136.                 Q[i].R=st[y];
  137.             }
  138.         }
  139.         K=(int)sqrt(2*n);
  140.         sort(Q,Q+q);
  141.         mos();
  142.         for(int i=0;i<q;i++){
  143.             if(ANS[i]==1) printf("Find\n");
  144.             else printf("NotFind\n");
  145.         }
  146.         printf("\n");
  147.     }
  148.  
  149. }
  150.  
Success #stdin #stdout 0s 6452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7jcu1j
language:
C++14 (gcc 8.3)
created:
5 years 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!