Cod sursa(job #2444300)

Utilizator MortemPlaiasu Iulia-Silvia Mortem Data 30 iulie 2019 23:53:03
Problema Heavy Path Decomposition Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.5 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

int n,m;
int a[100500];
int nrS[100500];
int lv[100500];
int p[100500];
bool vis[100500];
std::vector<int> v[100500];
std::vector<int> chain[100500];
int listId[100500];
int listPl[100500];
int currentId;

int ** arb;

int dfs(int nod)
{
  int maxsons=0;
  int posmax;
  nrS[nod]=1;
  vis[nod]=true;
  bool end=true;
  for(unsigned int i=0;i<v[nod].size();i++)
  {
    int elem = v[nod][i];
    if(!vis[elem])
    {
      end=false;
      p[elem]= nod;
      lv[elem]=lv[nod]+1;
      int sons = dfs(elem);
      nrS[nod]+=sons;
      if(sons>maxsons)
      {
        maxsons=sons;
        posmax=elem;
      }
    }
  }
  if(end)
  {
    listId[nod]=currentId;
    chain[currentId].push_back(nod);
    listPl[nod]=chain[currentId].size()-1;
    currentId++;
  }
  else
  {
    int crntId=listId[posmax];
    listId[nod]=crntId;
    chain[crntId].push_back(nod);
    listPl[nod]=chain[crntId].size()-1;
  }
  return nrS[nod];
}

void update(int ind,int pos)
{
  arb[ind][pos]=std::max(arb[ind][2*pos+1],arb[ind][2*pos+2]);
  if(pos==0) return;
  update(ind,(pos-1)/2);
}

void pushT(int ind, int x, int low, int high,int pos)
{
  int m= (low+high)/2;
  int l = chain[ind][x];
  if(low==high)
  {
    arb[ind][pos]=a[l];
    if(pos!=0)
      update(ind,(pos-1)/2);
    return;
  }
  if(x<=m)
    pushT(ind,x,low,m,2*pos+1);
  else
    pushT(ind,x,m+1,high,2*pos+2);
}

int query(int ind, int a, int b, int low, int high, int pos)
{
  int m= (high+low)/2;
  if(b<low || a>high) return -1;
  if(low==high && low>=a && low<=b) return arb[ind][pos];
  int max1= -1;
  int max2= -1;
  if(b>=m+1)
    max1= query(ind,a,b,m+1,high,2*pos+2);
  if(a<=m)
    max2= query(ind,a,b,low,m,2*pos+1);
  return std::max(max1,max2);
}

int climb(int nod,int LI, int maxLv)
{
  if(listId[nod]!=LI && lv[nod]>maxLv)
    return climb(p[nod],LI,maxLv);
  return nod;
}


int main()
{
  freopen("heavypath.in","r",stdin);
  freopen("heavypath.out","w",stdout);
  scanf("%d %d",&n,&m);
  for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
  for(int i=0;i<n-1;i++)
  {
    int j,k;
    scanf("%d %d",&j,&k);
    v[j].push_back(k);
    v[k].push_back(j);
  }
  lv[1]=0;
  dfs(1);
  for(int i=0;i<currentId;i++)
  {
    int siz = chain[i].size();
    for(int j=0;j<(siz+1)/2;j++)
    {
      listPl[chain[i][j]]=siz-1-j;
      listPl[chain[i][siz-1-j]]=j;
      std::swap(chain[i][j],chain[i][siz-1-j]);
    }
  }
  arb = new int*[currentId+1];
  for(int i=0;i<currentId;i++)
  {
    int siz = chain[i].size();
    arb[i]= new int[4*siz];
    for(int j=0;j<siz;j++)
      pushT(i,j,0,siz-1,0);
  //  writearb(i);
  }
  for(int i=0;i<m;i++)
  {
    int c, x, y;
    scanf("%d %d %d",&c,&x,&y);
    if(c==0)
    {
      int ind= listId[x];
      a[x]=y;
      pushT(ind,listPl[x],0,chain[ind].size()-1,0);
     // writearb(ind);
    }
    else
    {
      int maxx=0;
      while (true)
      {
        int l1= listId[x];
        int l2= listId[y];
        if(l1==l2)
        {
          int lpmin= std::min(listPl[x],listPl[y]);
          int lpmax= std::max(listPl[x],listPl[y]);
          maxx=std::max(maxx,query(l1,lpmin, lpmax,0,chain[l1].size()-1,0 ));
          break;
        }
        else
        {
          if(lv[chain[l1][0]]<lv[chain[l2][0]])
          {
            std::swap(x,y);
            std::swap(l1,l2);
          }
          maxx= std::max(maxx,query(l1,0,listPl[x],0,chain[l1].size()-1,0));
          x=p[chain[l1][0]];
        //  std::cout<<maxx<<"\n";
        }
      }
      std::cout<<maxx<<"\n";
    }
  }
}