算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
题目描述:
    给一颗结点数为(100,000)的树,最多询问100,000次。每次询问对两个结点X,Y,以X为根,Y的最小标号的孩子,Y的最小标号的后代。
吐槽:
    1. 这么难写的题为什么大家都当水题做阿...
算法分析:
    
    对于X,Y,我们求出其LCA,U。
    如果U是Y的父亲,那么一切都不变。用预处理的结果就可以。
    如果U是Y,那么我们可以快速求出,含有后代X的Y的儿子X'。
    检查X'是否是Y的最小孩子(儿子)。如果是,那么结果是Y的次小儿子(孩子)。否则是Y的最小儿子(孩子)。
    于是我们树形DP,求出最小与次小(儿子,后代)就可以了。写起来很猥琐,容易出错。
    LCA的写法是参照shi哥的代码。
    先预处理求出u的(1,2,4,8,...)代祖先,
    先让x,y处于同一层。
    然后让x,y一点一点向上爬,直到爬到恰好x==y的位置就是LCA了。
    
#include<iostream>
#include<cassert>
#include<cstdio>
using namespace std;
const int maxb = 17;
const int V = 1<<maxb;
int e,P[V][maxb], head[V], nxt[V<<1], pnt[V<<1], mn[V], sd[V], mn1[V],sd1[V];
// dp
const int inf = ~0u>>2;
int dep[V];
void dfs(int u,int f){
    P[u][0] = f;
    for(int i =1; i< maxb; i++)
        P[u][i] = P[P[u][i-1]][i-1];
    if(f!=u) mn[u] = f; else mn[u] = inf;
    mn1[u] = sd1[u] = inf;
    sd[u] = inf;
    for(int i=head[u];i!=-1;i=nxt[i]) {
        int v = pnt[i];
        if(v == f) continue;
        dep[v] = dep[u] + 1;
        if(v < mn[u]) {sd[u] = mn[u]; mn[u] = v;}
        else if(v < sd[u]) sd[u] = v;
        dfs(v,u);
        int fst,snd;
        if(v > mn1[v]) {
            fst = mn1[v];
            snd = min(v, sd1[v]);
        }
        else {
            fst = v;
            snd = mn1[v];
        }
        if(fst < mn1[u]){
            sd1[u] = mn1[u];
            mn1[u] = fst;
        }
        else {
            sd1[u] = min(sd1[u],fst);
        }
    }
}
// build
void add(int u,int v){
    nxt[e] = head[u];
    head[u] = e;
    pnt[e++] = v;
}
// LCA
void go(int &u,int d){
    for(int i=0;i<maxb;i++){
        if((1<<i) & d) u = P[u][i];
    }
}
int LCA(int x,int y){
    if(dep[x] > dep[y]) swap(x,y);
    go(y,dep[y] - dep[x]);
    if(x == y) return x;
    for(int i=maxb-1;i>=0;i--){
        if(P[x][i] != P[y][i])
            x = P[x][i], y = P[y][i];
    }
    assert(P[x][0]==P[y][0]);
    return P[x][0];
}
// work
void work(int x,int y){
    int u = LCA(x,y);
    if(sd[y] == inf) {puts("no answers!"); return;}
    if(u!=y){
        printf("%d %d\n",P[y][0] == mn[y] ? sd[y] : mn[y], mn1[y]);
    }
    else {
        go(x,dep[x]-dep[y]-1);
        
        printf("%d %d\n",x == mn[y] ? sd[y]: mn[y] , y == 1 ? (min(mn1[x],x) == mn1[y]? sd1[y]: mn1[y]): 1);
    }
}
int main(){
    int test;
    scanf("%d",&test);
    while(test--){
        int u,v,n,m;
        e = 0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) head[i] = -1;
        for(int i=1;i<n;i++){
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        dep[1] = 0;
        dfs(1,1);
        while(m--){
            scanf("%d%d",&u,&v);
            work(u,v);
        }
        puts("");
    }
}
posted on 2012-07-17 10:53 西月弦 阅读(483) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理