11月1日上午T2

$T o n y Z h a o 的代理服務節點遍布全球。但是他想要去開辟新的領域（比如在大合唱上放音樂 OvO ）,于是便將這些節點的控制系統交給了小花。$

小花研究了很長時間，發現整個系統是由 $aia_ia?i?? 號節點訪問 bib_ib?i?? 號節點上的數據。$

分配系統路線的事情當然是全自動完成的，路徑分配系統是 $TonyZhao\mathfrak{TonyZhao}TonyZhao 寫的——它的算法確保了路徑不會經過同一條網線兩次。（當然所有網線帶寬均 >0\gt 0>0 ）但是小花得到了一個任務——她要對整個系統進行更新，也就是要更換網線。為了升級，她需要知道客戶的特殊信息——他們的訪問路徑上所有經過網線中最大的帶寬和最小的帶寬。這很有利于工程師們分析升級方案，但是并沒有可用的系統可以做到這一點。小花于是想到求助 NOIP 2017 將會輕松 AK 的你，請你幫一幫她。$

$這道題用到了倍增lca，同時倍增求出最大最小值$

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int ans1,ans2,val[500005];
int n,m,s,head[500005],nxt[1200000],to[1200000],ce,dep[500005],fa[500005][22],lg[500005],maxx[500005][22],minn[500005][22];
void add(int u,int v,int w){
    to[++ce]=v;nxt[ce]=head[u];head[u]=ce;val[ce]=w;
}
void dfs(int now,int fat){
    dep[now]=dep[fat]+1;
    fa[now][0]=fat;
    for(int i=1;(1<<i)<=dep[now];i++){
        fa[now][i]=fa[fa[now][i-1]][i-1];
        maxx[now][i]=max(maxx[now][i-1],maxx[fa[now][i-1]][i-1]);
        minn[now][i]=min(minn[now][i-1],minn[fa[now][i-1]][i-1]);
    }
    for(int i=head[now];i;i=nxt[i])
        if(to[i]!=fat){
            maxx[to[i]][0]=val[i];
            minn[to[i]][0]=val[i];
          //  printf("%d %d\n",maxx[to[i]][0],minn[to[i]][0]);
            //printf("%d ",val[1]);
            dfs(to[i],now);
        }
}
int lca(int x,int y){
    if(dep[x]<dep[y])
        swap(x,y);
    while(dep[x]>dep[y]){
        ans1=max(ans1,maxx[x][lg[dep[x]-dep[y]]-1]);
        ans2=min(ans2,minn[x][lg[dep[x]-dep[y]]-1]);
        x=fa[x][lg[dep[x]-dep[y]]-1];
    }
    if(x==y) return x;
    for(int i=lg[dep[x]]-1;i>=0;i--)
        if(fa[x][i]!=fa[y][i]){
            int maxn=max(maxx[x][i],maxx[y][i]);
            ans1=max(ans1,maxn);
            int mi=min(minn[x][i],minn[y][i]);
            ans2=min(ans2,mi);
            x=fa[x][i],y=fa[y][i];
        }
    return fa[x][0];
}
int main(){
   // freopen("r.in","r",stdin);
   // freopen("r.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);add(b,a,c);
       //printf("%d\n",val[ce]);
    }
   // printf("%d",val[2]);
    maxx[1][0]=-1,minn[1][0]=2147483647;
    dfs(1,0);
    for(int i=1;i<=n;i++)
        lg[i]=lg[i-1]+((1<<lg[i-1])==i);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        ans1=-1,ans2=2147483647;
        int x,y;
        scanf("%d%d",&x,&y);
        lca(x,y);
        printf("%d %d\n",ans1,ans2);
        //printf("%d\n",lca(x,y));    
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=20;j++)
            printf("%d %d %d\n",i,j,maxx[i][j]);

    return 0;
}

posted @ 2018-11-01 14:00 NGU_AlexZhang 閱讀(151) 評論(0) 收藏舉報

刷新頁面返回頂部

11月1日上午T2

公告