本文共 2244 字，大约阅读时间需要 7 分钟。
题意：给你一棵树，询问u到v路径上的第k大
题解：从u到v的路径能想到，u到根+v到根-lca（u，v）到根-fa[lca(u,v)]到根剩下的就是u到v之间的路径。因此只要离散化一下，每次dfs的时候处理倍增lca和主席树更新操作就可以
#include #include #include #include #include #include #include #include #include #include #include //CLOCKS_PER_SEC#define se second#define fi first#define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define Pii pair #define Pli pair #define ull unsigned long long#define pb push_back#define fio ios::sync_with_stdio(false);cin.tie(0)const double Pi=3.14159265;const int N=1e5+10;const ull base=163;const int INF=0x3f3f3f3f;using namespace std;int n,m, root[N], a[N],cnt=0;struct node { int l,r,sum;}T[40*N];int New[N];int fa[N][20];int dep[N];vector v;int head[N],to[2*N],nx[2*N],tot=1;void add(int u,int v){ to[tot]=v; nx[tot]=head[u]; head[u]=tot++;}int getid(int x){ return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}void update(int l,int r,int &x,int y,int pos){ T[++cnt]=T[y],T[cnt].sum++,x=cnt; if(l==r)return ; int m=(l+r)>>1; if(pos<=m)update(l,m,T[x].l,T[y].l,pos); else update(m+1,r,T[x].r,T[y].r,pos);}void dfs(int u,int pre){ fa[u][0]=pre; dep[u]=dep[pre]+1; update(1,n,root[u],root[pre],New[u]); for(int i=1;i<17;i++){ fa[u][i]=fa[fa[u][i-1]][i-1]; } for(int i=head[u];i;i=nx[i]){ int v=to[i]; if(pre==v)continue; dfs(v,u); }}int LCA(int u,int v){ if(dep[u] =0;i--){ if(fa[v][i]!=fa[u][i]){ u=fa[u][i]; v=fa[v][i]; } } return fa[u][0];}int query(int l,int r,int k,int x,int y,int z,int w){ if(l==r)return l; int m=(l+r)>>1; int d=T[T[x].l].sum+T[T[y].l].sum-T[T[z].l].sum-T[T[w].l].sum; if(d>=k)return query(l,m,k,T[x].l,T[y].l,T[z].l,T[w].l); else return query(m+1,r,k-d,T[x].r,T[y].r,T[z].r,T[w].r);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.pb(a[i]); sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end()); for(int i=1;i<=n;i++)New[i]=getid(a[i]); for(int i=1;i<=n-1;i++){ int u,v;scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs(1,0); for(int i=1;i<=m;i++){ int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d\n",v[query(1,n,k,root[l],root[r],root[LCA(l,r)],root[fa[LCA(l,r)][0]])-1]); } return 0;}
转载于:https://www.cnblogs.com/Mrleon/p/9097900.html