题目大意: 给定一棵 N 个节点的树, 点有点权, 要求回答 M 个询问, 每次询问点 u 到点 v 的简单路径 (链) 上权值第 K 小是多少.
题解: 学习到了树上主席树.
主席树维护序列时, 每次将后一个点的树建立在前一个点的树上, 由此构成一个前缀和, 并利用可以在线段树上二分的性质来求 K 小值. 树上主席树维护的是每个节点到根节点路径上的前缀和, 即: 每个点的主席树建立在其父节点的主席树基础上. 回答答案时, 只需在 u,v,lca(u,v),fa[lca(u,v)] 的四棵主席树上面二分答案即可.
代码如下
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- const int maxn=1e5+10;
- int n,m,val[maxn],d[maxn],len;
- int f[maxn][21],dep[maxn];
- struct Graph{
- int nxt,to;
- }e[maxn<<1];
- int tot=1,head[maxn];
- inline void add_edge(int from,int to){
- e[++tot]=(Graph){head[from],to},head[from]=tot;
- }
- struct node{
- #define ls(x) t[x].lc
- #define rs(x) t[x].rc
- int lc,rc,sum;
- }t[maxn*20];
- int cnt,root[maxn];
- inline void pushup(int o){t[o].sum=t[ls(o)].sum+t[rs(o)].sum;}
- int insert(int pre,int l,int r,int pos,int value){
- int o=++cnt;
- t[o]=t[pre];
- if(l==r){t[o].sum+=value;return o;}
- int mid=l+r>>1;
- if(pos<=mid)ls(o)=insert(ls(pre),l,mid,pos,value);
- else rs(o)=insert(rs(pre),mid+1,r,pos,value);
- return pushup(o),o;
- }
- int query(int a,int b,int c,int d,int l,int r,int k){
- if(l==r)return l;
- int mid=l+r>>1;
- int sum=t[ls(c)].sum+t[ls(d)].sum-t[ls(a)].sum-t[ls(b)].sum;
- if(k<=sum)return query(ls(a),ls(b),ls(c),ls(d),l,mid,k);
- else return query(rs(a),rs(b),rs(c),rs(d),mid+1,r,k-sum);
- }
- inline int ask(int x){return lower_bound(d+1,d+len+1,x)-d;}
- void read_and_parse(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)scanf("%d",&val[i]),d[++len]=val[i];
- for(int i=1,x,y;i<n;i++){
- scanf("%d%d",&x,&y);
- add_edge(x,y),add_edge(y,x);
- }
- sort(d+1,d+len+1);
- len=unique(d+1,d+len+1)-d-1;
- }
- void dfs(int u,int fa){
- dep[u]=dep[fa]+1,f[u][0]=fa;
- for(int i=1;i<=20;i++)f[u][i]=f[f[u][i-1]][i-1];
- root[u]=insert(root[fa],1,len,ask(val[u]),1);
- for(int i=head[u];i;i=e[i].nxt){
- int v=e[i].to;if(v==fa)continue;
- dfs(v,u);
- }
- }
- int lca(int x,int y){
- if(dep[x]<dep[y])swap(x,y);
- for(int i=18;~i;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];
- if(x==y)return x;
- for(int i=18;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
- return f[x][0];
- }
- void solve(){
- int lastans=0;
- dfs(1,0);
- while(m--){
- int x,y,k;
- scanf("%d%d%d",&x,&y,&k);
- x=lastans^x;
- int z=lca(x,y);
- printf("%d\n",lastans=d[query(root[f[z][0]],root[z],root[x],root[y],1,len,k)]);
- }
- }
- int main(){
- read_and_parse();
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2975263.html