hdu_4916 Count on the path

题目:

  bobo has a tree, whose vertices are conveniently labeled by 1,2,…,n.
  Let f(a,b) be the minimum of vertices not on the path between vertices a and b.
  There are q queries (u i,v i) for the value of f(u i,v i). Help bobo answer them.

思路:

  把作为根节点,如果不等于,那么最小值一定是。所以接下来只用考虑穿过的情况。
  设点的祖先中深度为的点(也就是的儿子)。剩下的点就能被分成三类,第一类:的子树中,除了以外的点。第二类:的子树中,除了以外的点。第三类:的儿子(除了)的子树中的点。前两类可以在dfs中直接预处理出来,第三类直接在处记录前小的值和来自哪个儿子即可。

代码:

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
#define clr(a,b) memset(a,b,sizeof a)
#define MN 1000005
#define inf 2100000000
using namespace std;
inline char Getchar(){
    static const int LEN=1000005;
    static char Buf[LEN],*OP=Buf,*ED=Buf;
    if(OP==ED){OP=Buf;ED=Buf+fread(Buf,1,LEN,stdin);}
    return OP==ED?EOF:*OP++;
}
bool read(int &x){
    static char c;
    for(c=Getchar();!isdigit(c);c=Getchar())if(c==EOF)return 0;
    for(x=0;isdigit(c);c=Getchar())x=(x<<1)+(x<<3)+c-'0';
    return 1;
}
template<class T> bool tomin(T &a,T b){return b<a?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<int N,int M,class T> struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void clear(){clr(HEAD,0);tot=0;}
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator [] (int x){return W[x];}
    #define EOR(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
};
Link<MN,MN<<1,int> G;
int hs[MN],siz[MN],tp[MN],fa[MN],dep[MN],Min[MN];
void dfs1(int o,int f){
    hs[o]=0;siz[o]=1;
    fa[o]=f;dep[o]=dep[f]+1;
    Min[o]=o;
    EOR(k,G,o){
        int v=G[k];
        if(v==f)continue;
        dfs1(v,o);
        tomin(Min[o],Min[v]);
        if(siz[hs[o]]<siz[v])hs[o]=v;
        siz[o]+=siz[v];
    }
}
void dfs2(int o,int f,int TP){
    tp[o]=TP;
    if(hs[o])dfs2(hs[o],o,TP);
    EOR(k,G,o){
        int v=G[k];
        if(v==f||v==hs[o])continue;
        dfs2(v,o,v);
    }
}
int anc[MN],val[MN];
void dfs(int o,int f,int Mn){
    if(o!=1){
        if(f==1)anc[o]=o;
        else anc[o]=anc[f];
    }
    int min1=inf,min2=inf,t1,t2;
    EOR(k,G,o){
        int v=G[k];
        if(v==f)continue;
        if(tomin(min2,Min[v]))t2=v;
        if(min2<min1)swap(min1,min2),swap(t1,t2);
    }
    if(tomin(min2,Mn))t2=0;
    if(min2<min1)swap(min1,min2),swap(t1,t2);
    val[o]=min1;
    EOR(k,G,o){
        int v=G[k];
        if(v==f)continue;
        if(v==t1)dfs(v,o,min2);
        else dfs(v,o,min1);
        tomin(val[o],Min[v]);
    }
}
int lca(int u,int v){
    while(tp[u]!=tp[v]){
        if(dep[fa[tp[u]]]<dep[fa[tp[v]]])
            swap(u,v);
        u=fa[tp[u]];
    }
    return dep[v]>dep[u]?u:v;
}
int Mn[3],t[3];
void init(){
    dfs1(1,0);dfs2(1,0,1);
    FOR(i,0,2)Mn[i]=inf;
    val[1]=inf;
    EOR(k,G,1){
        int v=G[k];
        dfs(v,1,inf);
        if(tomin(Mn[2],Min[v]))t[2]=v;
        DOR(i,2,1)
            if(Mn[i]<Mn[i-1]){
                swap(Mn[i],Mn[i-1]);
                swap(t[i],t[i-1]);
            }
            else break;
    }
}
int query(int u,int v){
    if(lca(u,v)!=1)return 1;
    int k=0,ans=min(val[u],val[v]);
    while(anc[u]==t[k]||anc[v]==t[k])k++;
    tomin(ans,Mn[k]);
    return ans;
}
int main(){
    int Q,n;
    //freopen("data.txt","r",stdin);
    while(read(n)&&read(Q)){
        G.clear();
        FOR(i,1,n-1){
            int a,b;
            read(a);read(b);
            G.add(a,b);G.add(b,a);
        }
        init();
        int lastans=0;
        FOR(i,1,Q){
            int a,b;
            read(a);read(b);
            a^=lastans;b^=lastans;
            printf("%d\n",lastans=query(a,b));
        }
    }
    return 0;
}