Cod sursa(job #1169492)

Utilizator teoionescuIonescu Teodor teoionescu Data 11 aprilie 2014 15:15:13
Problema Heavy Path Decomposition Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.13 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
ifstream in("heavypath.in");
ofstream out("heavypath.out");
const int size=1<<8;
char buff[size+1];
int pos=size+1;
inline bool rable(char& c){return ('0'<=c && c<='9');}
void Read(int& x){
    x=0;
    if(pos>=size) in.read(buff,size),pos=0;
    while(!rable(buff[pos])){
        pos++;
        if(pos>=size) in.read(buff,size),pos=0;
    }
    while(rable(buff[pos])){
        x=x*10 + int(buff[pos]) - '0';
        pos++;
        if(pos>=size) in.read(buff,size),pos=0;
    }
}
const int Nmax = 100002;
int mark[Nmax],H[Nmax],L[Nmax],First[Nmax];
vector<int> G[Nmax];
int v[Nmax];
vector<int> Chains[Nmax];
int NumChains,ChainFather[Nmax],PartOfChain[Nmax],Catelea[Nmax];

int DfsH(int x,int lev){
    mark[x]=1;
    L[x]=lev;
    for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it){
        if(!mark[*it]) H[x]+=DfsH(*it,lev+1);
    }
    return H[x]+1;
}

void DfsChain(int x,int wh){
    mark[x]=1;
    Chains[wh].push_back(x);
    PartOfChain[x]=wh;
    Catelea[x]=Chains[wh].size();
    int maxh=-1,maxw;
    for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it){
        if(!mark[*it]){
            if(H[*it]>maxh) maxh=H[*it],maxw=*it;
        }
    }
    for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it){
        if(!mark[*it]){
            if(*it==maxw) DfsChain(*it,wh);
            else{
                ChainFather[++NumChains]=x;
                DfsChain(*it,NumChains);
            }
        }
    }
}

struct Aint{
    vector<int> A;
    int Size;
    void Update(int i,int st,int dr,int wh,int val){
        if(st>=dr) A[i]=val;
        else{
            int mij=(st+dr)/2;
            if(wh<=mij) Update(2*i,st,mij,wh,val);
            else Update(2*i+1,mij+1,dr,wh,val);
            A[i]=max(A[2*i],A[2*i+1]);
        }
    }
    int Query(int i,int st,int dr,int a,int b){
        if(a<=st && dr<=b) return A[i];
        else{
            int mij=(st+dr)/2;
            if(b<=mij) return Query(2*i,st,mij,a,b);
            else if(a>mij) return Query(2*i+1,mij+1,dr,a,b);
            else{
                int aa=Query(2*i,st,mij,a,mij);
                int bb=Query(2*i+1,mij+1,dr,mij+1,b);
                return max(aa,bb);
            }
        }
    }
    void update(int wh,int val){
        Update(1,1,Size,wh,val);
    }
    int query(int a,int b){
        return Query(1,1,Size,a,b);
    }
    Aint(){}
    Aint(vector<int> V){
        Size=V.size();
        A=vector<int>(4*(Size)+2); // theoretically 4n+1
        for(int i=0;i<V.size();i++) update(i+1,v[V[i]]);
    }
};
vector<Aint> Aints;

int ChainQuery(int x,int y){
    int Max=0;
    int cx=PartOfChain[x];
    int cy=PartOfChain[y];
    while(cx!=cy){
        int px=ChainFather[cx];
        int py=ChainFather[cy];
        if(L[px]>L[py]){
            Max=max(Max,Aints[cx-1].query(1,Catelea[x]));
            x=ChainFather[cx];
            cx=PartOfChain[x];
        }
        else{
            Max=max(Max,Aints[cy-1].query(1,Catelea[y]));
            y=ChainFather[cy];
            cy=PartOfChain[y];
        }
    }
    x=Catelea[x];
    y=Catelea[y];
    if(x>y) swap(x,y);
    Max=max(Max,Aints[cx-1].query(x,y));
    return Max;
}

int N,M;
int main(){
    Read(N);
    Read(M);
    for(int i=1;i<=N;i++) Read(v[i]);
    for(int i=1;i<N;i++){
        int x,y;
        Read(x);
        Read(y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int root=1;
    memset(mark,0,sizeof(mark)); DfsH(root,1);
    memset(mark,0,sizeof(mark)); DfsChain(root,++NumChains);
    Aints=vector<Aint>(NumChains+1);
    for(int i=1;i<=NumChains;i++) Aints[i-1]=( Aint(Chains[i]) );
    for(int i=1;i<=M;i++){
        int t,x,y;
        Read(t);
        Read(x);
        Read(y);
        if(t==0){
            v[x]=y;
            Aints[PartOfChain[x]-1].update(Catelea[x],y);
        }
        if(t==1){
            out<<ChainQuery(x,y)<<'\n';
        }
    }
    return 0;
}