本文共 2694 字，大约阅读时间需要 8 分钟。
又是一道简单题
给出一棵有根树，每次查询给出两个节点 u 和 v，假设节点 f 是u，v的最近公共祖先，请查询以 f 为根的子树中，不在 u 到 v 这条链上且标号最小的节点。
输入格式
第一行输入正整数 T（T <= 30），表示共有T组输入数据。
对于每组数据，第一行输入两个正整数 n，m（n <= 50000，m <= 50000），表示节点数和询问数，节点编号 1 到 n，其中 1 是根节点。
接下来 n - 1 行，每行输入两个正整数u，v，表示标号为u和v的节点间有一条边。
接下来 m 行，每行输入两个正整数u，v，表示一次询问。
保证所有输入数据均合法。
输出格式
对于每次询问，输出答案。如不存在输出-1。
13 31 21 31 21 32 3
32-1 分析：考虑树链剖分； 把子树按dfs序可以展开到一维，然后对于链，可以将这个区间分成logn的部分，对于每个部分求最小值即可； 复杂度nlognlogn； 代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,m,n) for(i=m;i<=n;i++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector #define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair #define ls rt<<1#define rs rt<<1|1#define sys system("pause")const int maxn=1e5+10;const int N=1e5+10;using namespace std;ll gcd(ll p,ll q){ return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){ if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;}int n,m,k,t,st[maxn],ed[maxn],dep[maxn],fa[20][maxn],bel[maxn],son[maxn],pos[maxn],a[maxn],dfs_cl,mi[maxn<<2];vi e[maxn];void dfs1(int x,int y){ dep[x]=dep[y]+1; fa[0][x]=y; son[x]=1; for(int i=1;fa[i-1][fa[i-1][x]];i++) { fa[i][x]=fa[i-1][fa[i-1][x]]; } for(int i=0;i son[ma])ma=z; } if(ma!=0)dfs2(ma,x,ch); for(int i=0;i =0;i--)if(dep[fa[i][x]]>=dep[y])x=fa[i][x]; if(x==y)return x; for(int i=19;i>=0;i--) { if(fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y]; } return fa[0][x];}void pup(int l,int r,int rt){ mi[rt]=min(mi[ls],mi[rs]);}void build(int l,int r,int rt){ if(l==r) { mi[rt]=a[l]; return; } int mid=l+r>>1; build(l,mid,ls); build(mid+1,r,rs); pup(l,r,rt);}int gao(int L,int R,int l,int r,int rt){ if(L==l&&R==r)return mi[rt]; int mid=l+r>>1; if(R<=mid)return gao(L,R,l,mid,ls); else if(L>mid)return gao(L,R,mid+1,r,rs); else return min(gao(L,mid,l,mid,ls),gao(mid+1,R,mid+1,r,rs));}void upd(vector &a,int x,int y){ while(bel[x]!=bel[y]) { if(dep[bel[x]] pos[y])swap(x,y); a.pb(pos[y]); a.pb(pos[x]);}int main(){ int i,j; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); rep(i,1,n)e[i].clear(); rep(i,1,n)rep(j,0,19)fa[j][i]=0; rep(i,1,n-1)scanf("%d%d",&j,&k),e[j].pb(k),e[k].pb(j); dfs1(1,0); dfs_cl=0; dfs2(1,0,1); build(1,n,1); while(m--) { int x,y; scanf("%d%d",&x,&y); vector tmp; int lc=lca(x,y); upd(tmp,x,y); int s=st[lc],t=ed[lc]; if(lc<1||lc>n)return 0; sort(tmp.begin(),tmp.end()); int mi=1e9; for(i=0;i
转载于:https://www.cnblogs.com/dyzll/p/6973627.html