fork download
copy 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<vector>
  4. #define pb push_back
  5. #define maxn 100005
  6. #define maxait 1<<20   //segment tree size
  7. using namespace std;
  8.  
  9. int n,m,nrp,nrl,sol;  
  10. int ait[maxait];
  11. int v[maxn],lev[maxn],nr[maxn],liniar[maxn];
  12. int pfather[maxn],path[maxn],lpos[maxn],start[maxn];
  13. vector <int> l[maxn],p[maxn];
  14.  
  15.  //n-number of nodes; m-number of queries; nrp-number of paths;
  16.  //nrl-number of elements of liniar[i]
  17.  //ait[i]-segment tree
  18.  //v[i]-value of node i;
  19.  //lev[i]-level of node i; nr[i]-number of nodes in the subtree of node i; 
  20.  //liniar[i]-paths concatenated
  21.  //pfather[i]-the node that represents the father of path i;
  22.  //path[i]-path of node i;
  23.  //lpos[i]-position of node i in liniar[]
  24.  //start[i]-start position of path i in vector liniar[]
  25.  //l[i]-list of nodes adjacent to node i
  26.  //p[i]-ith path
  27.  
  28. void read()
  29. {
  30.     int x,y;
  31.     scanf("%d%d",&n,&m);
  32.     for(int i=1;i<=n;i++) scanf("%d",&v[i]);
  33.     for(int i=1;i<n;i++)
  34.     {
  35.         scanf("%d%d",&x,&y);
  36.         l[x].pb(y); l[y].pb(x);   //bidirectional edge between nodes x and y
  37.     }
  38. }
  39.  
  40. void dfs(int k,int level,int father) //k-current node,level-clevel,father-cfather
  41. {
  42.     int nrc=0,ind;                //nrc-maximum nodes int the subtree of a son and ind=son index
  43.     lev[k]=level; nr[k]=1; 
  44.     for(unsigned int i=0;i<l[k].size();i++) // for all adjacent nodes to k
  45.      if(!lev[l[k][i]]) //not visited
  46.      {
  47.          dfs(l[k][i],level+1,k); //next node
  48.          nr[k]+=nr[l[k][i]]; //we add the number of nodes in the subtree of a son to the father total
  49.          if(nr[l[k][i]]>nrc) nrc=nr[l[k][i]],ind=l[k][i]; 
  50.      }
  51.  
  52.  	//if leaf then make a new path that contains only k
  53.     if(l[k].size()==1 && k!=1) p[++nrp].pb(k),path[k]=nrp,pfather[nrp]=father;
  54.     else p[path[ind]].pb(k),path[k]=path[ind],pfather[path[ind]]=father;
  55.     //else add the node to the heavyest path 
  56. }
  57.  
  58. void build(int k,int left,int right)
  59. {
  60.     if(left==right) {ait[k]=v[liniar[left]]; return;}
  61.     int mid=(left+right)>>1;
  62.     build(2*k,left,mid);
  63.     build(2*k+1,mid+1,right);
  64.     ait[k]=max(ait[2*k],ait[2*k+1]);
  65. }
  66.  
  67. void make_paths()
  68. {
  69.     for(int k=1;k<=nrp;k++)
  70.     {
  71.         start[k]=nrl+1;
  72.         reverse(p[k].begin(),p[k].end()); //reverse the path order
  73.         for(unsigned int i=0;i<p[k].size();i++)
  74.           liniar[++nrl]=p[k][i],lpos[p[k][i]]=nrl; //add paths to liniar[]
  75.           //maintain positions and pathstart
  76.     }
  77.     build(1,1,n); //build the segment tree on liniar[]
  78. }
  79.  
  80. void update(int k,int left,int right,int posc)
  81. {
  82.     if(left==right) {ait[k]=v[liniar[left]]; return;}
  83.     int mid=(left+right)>>1;
  84.     if(posc<=mid) update(2*k,left,mid,posc);
  85.     else update(2*k+1,mid+1,right,posc);
  86.  
  87.     ait[k]=max(ait[2*k],ait[2*k+1]);
  88. }
  89.  
  90. void query(int k,int left,int right,int x,int y)
  91. {
  92.     if( x<=left && right<=y ) {sol=max(sol,ait[k]); return;}
  93.     int mid=(left+right)>>1;
  94.     if(x<=mid) query(2*k,left,mid,x,y);
  95.     if(y>mid) query(2*k+1,mid+1,right,x,y);
  96. }
  97.  
  98. void solve()
  99. {
  100.     int type,x,y;
  101.     for(int i=1;i<=m;i++)
  102.     {
  103.         scanf("%d%d%d",&type,&x,&y);
  104.         if(!type)
  105.         {
  106.             v[x]=y;
  107.             update(1,1,n,lpos[x]); //change the value of node x to y
  108.             continue;
  109.         }
  110.         sol=0;
  111.         while(path[x]!=path[y])
  112.         {
  113.             if(lev[pfather[path[x]]]<lev[pfather[path[y]]]) swap(x,y);
  114.             query(1,1,n,start[path[x]],lpos[x]);
  115.             x=pfather[path[x]];
  116.         }
  117.         if(lpos[x]>lpos[y]) swap(x,y);
  118.         query(1,1,n,lpos[x],lpos[y]); //get the query answer in sol
  119.         printf("%d\n",sol);
  120.     }
  121. }
  122.  
  123. int main()
  124. {
  125.     freopen("heavypath.in","r",stdin);
  126.     freopen("heavypath.out","w",stdout);
  127.  
  128.     read(); 
  129.     dfs(1,1,0);    //get the paths
  130.     make_paths();  //concatenate the paths 
  131.     solve();       //solve the queries
  132.  
  133.     fclose(stdin);
  134.     fclose(stdout);
  135.     return 0;
  136. }
Runtime error #stdin #stdout 0s 21096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HOeNbs
language:
C++14 (gcc 8.3)
created:
10 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!