Cod sursa(job #2738378)

Utilizator betybety bety bety Data 5 aprilie 2021 19:29:30
Problema Heavy Path Decomposition Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.46 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("heavypath.in");
ofstream out("heavypath.out");
const int lim=1e5+4;
vector<int> vec[lim];
int vv[lim];
int dim[lim];
bool ok[lim];
int tata[lim];
int nr_path[lim];
int poz_path[lim];
struct path
{
    int tata;
    vector<int> v;
    vector<int> tree;
    void btree(){
        tree.resize(4*v.size(),0);
    }
    void build(int nod,int l,int r){
        if(l==r){
            tree[nod]=v[l];
            return ;
        }
        int med=(l+r)/2;
        build(2*nod,l,med);
        build(2*nod+1,med+1,r);
        tree[nod]=max(tree[2*nod],tree[2*nod+1]);
    }
    void update(int nod,int l,int r,int poz){
        if(l==r){
            tree[nod]=v[l];
            return ;
        }
        int med=(l+r)/2;
        if(poz<=med)
            update(2*nod,l,med,poz);
        else update(2*nod+1,med+1,r,poz);
        tree[nod]=max(tree[2*nod],tree[2*nod+1]);
    }
    int query(int nod,int l,int r,int a,int b){
        if(a<=l and r<=b)
            return tree[nod];
        int med=(l+r)/2,ans1=0,ans2=0;
        if(a<=med) ans1=query(2*nod,l,med,a,b);
        if(b>med) ans2=query(2*nod+1,med+1,r,a,b);
        return max(ans1,ans2);
    }
};
int ad[lim];
path* p[lim];
int cnt=1;
void predf(int nod)
{
    ok[nod]=true;
    dim[nod]=1;
    for(int x:vec[nod])
    if(!ok[x])
    {
        ad[x]=ad[nod]+1;
        predf(x);
        tata[x]=nod;
        dim[nod]+=dim[x];
    }
}
void df(int nod,int unde)
{
    poz_path[nod]=p[unde]->v.size();
    p[unde]->v.push_back(vv[nod]);
    nr_path[nod]=unde;
    int biggest=0,maxim=0;
    for(int x:vec[nod])
    if(tata[x]==nod)
    {
        if(dim[x]>maxim)
        {
            maxim=dim[x];
            biggest=x;
        }
    }
    for(int x:vec[nod])
    if(tata[x]==nod)
    {
        if(biggest==x)
            df(x,unde);
        else
        {
            ++cnt;
            p[cnt]=new path;
            p[cnt]->tata=x;
            p[cnt]->v.push_back(0);
            df(x,cnt);
        }
    }
}
int n,q,t,x,y;
int main()
{
    in>>n>>q;
    for(int i=1;i<=n;++i)
        in>>vv[i];
    for(int i=1;i<n;++i)
    {
        in>>x>>y;
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    p[1]=new path;
    p[1]->tata=1;
    p[1]->v.push_back(0);
    predf(1);
    df(1,1);
    for(int i=1;i<=cnt;++i)
    {
        p[i]->btree();
        p[i]->build(1,1,p[i]->v.size()-1);
    }
    while(q--)
    {
        in>>t>>x>>y;
        if(t==1)
        {
            int ans=0;
            while(nr_path[x]!=nr_path[y])
            {
                if(ad[p[nr_path[x]]->tata]>ad[p[nr_path[y]]->tata])
                {
                    ans=max(ans,p[nr_path[x]]->query(1,1,p[nr_path[x]]->v.size()-1,1,poz_path[x]));
                    x=tata[p[nr_path[x]]->tata];
                }
                else
                {
                    ans=max(ans,p[nr_path[y]]->query(1,1,p[nr_path[y]]->v.size()-1,1,poz_path[y]));
                    y=tata[p[nr_path[y]]->tata];
                }
            }
            ans=max(ans,p[nr_path[x]]->query(1,1,p[nr_path[x]]->v.size()-1,min(poz_path[x],poz_path[y]),max(poz_path[x],poz_path[y])));
            out<<ans<<'\n';
        }
        else
        {
            p[nr_path[x]]->v[poz_path[x]]=y;
            p[nr_path[x]]->update(1,1,p[nr_path[x]]->v.size()-1,poz_path[x]);
        }
    }
    return 0;
}