6
16
2014
1

Tree Doubling Algorithm

namespace tda{
    const int N=100000,L=17;
    vector<int>to[N+10],we[N+10];
    int up[N+10][L+10],dp[N+10];
    pair<int,int>mx[N+10][L+10];
    pair<int,int>merge(pair<int,int>x,pair<int,int>y){
        static int t[4];
        t[0]=x.first;t[1]=x.second;
        t[2]=y.first;t[3]=y.second;
        sort(t,t+4,greater<int>());
        unique(t,t+4);
        return make_pair(t[0],t[1]);
    }
    void add(int u,int v,int w){
        to[u].push_back(v);we[u].push_back(w);
        to[v].push_back(u);we[v].push_back(w);
    }
    void build(){
        static int vis[N+10];
        queue<int>qu;qu.push(1);vis[1]=1;
        while(!qu.empty()){
            int u=qu.front();qu.pop();
            for(int i=1;i<=L;++i){
                up[u][i]=up[up[u][i-1]][i-1];
                mx[u][i]=merge(mx[u][i-1],mx[up[u][i-1]][i-1]);
            }
            for(int i=0;i<to[u].size();++i){
                int v=to[u][i],w=we[u][i];
                if(!vis[v]){
                    vis[v]=1;up[v][0]=u;
                    mx[v][0]=make_pair(w,-(~0u>>1));
                    dp[v]=dp[u]+1;qu.push(v);
                }
            }
        }
    }
    pair<int,int>query(int u,int v){
        pair<int,int>ans(-(~0u>>1),-(~0u>>1)); 
        if(dp[u]<dp[v])swap(u,v);
        for(int i=0;i<=L;++i)
            if(((dp[u]-dp[v])>>i)&1){
                ans=merge(ans,mx[u][i]);
                u=up[u][i];
            }
        if(u==v)return ans;
        for(int i=L;i>=0;--i)
            if(up[u][i]!=up[v][i]){
                ans=merge(ans,mx[u][i]);
                ans=merge(ans,mx[v][i]);
                u=up[u][i];
                v=up[v][i];
            }
        ans=merge(ans,mx[u][0]);
        ans=merge(ans,mx[v][0]);
        return ans;
    }
}
Category: 未分类 | Tags: | Read Count: 382
Avatar_small
boardmodelpaper.com 说:
2024年1月21日 01:05

The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. boardmodelpaper.com Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy, helping them familiarize themselves with the exam pattern and refine their understanding of the subject matter.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com