郑州网站建设 郑州网站设计,我想做网站卖衣服做,重庆市公共资源交易中心官网,论坛门户静态网页模板P2633 Count on a tree
题意#xff1a;
给定一棵 n 个节点的树#xff0c;每个点有一个权值。有 m 个询问#xff0c;每次给你 u,v,k#xff0c;你需要回答 u xor last 和 v 这两个节点间第 k 小的点权。
其中last 是上一个询问的答案#xff0c;定义其初始为 0#…P2633 Count on a tree
题意
给定一棵 n 个节点的树每个点有一个权值。有 m 个询问每次给你 u,v,k你需要回答 u xor last 和 v 这两个节点间第 k 小的点权。
其中last 是上一个询问的答案定义其初始为 0即第一个询问的 u 是明文。
题解
很明显主席树而且强制在线(更是主席树) 主席树是维护了一个类似前缀和的数据结构当要查询线性区间[l,r]的第k小时用第r个线段树减第l-1个线段树得到的就是[l,r]之间的权值线段树(因为主席树维护的就是前缀和)然后直接用二分查找第k小就行 在本题中给了一个树问点u到点v之间的第k小我们都知道树上差分(应该都知道)我们利用树上差分就可以得到u到v之间的数据 定义s[u]为从根节点到点u节点的主席树那么u到v之间的所有数值信息的主席树就应该是 s[u]s[v]-s[lca[u,v]]-s[fa[lca(u,v)]] 因为需要lca所以要用到倍增可以在dfs中插入每个点
代码 #includebits/stdc.h
using namespace std;
#define N 100010
#define M 2000010
int read(){int ans0,w1;char cgetchar();while(c!-!isdigit(c))cgetchar();if(c-)w-1,cgetchar();while(isdigit(c))ansans*10c-0,cgetchar();return ans*w;
}
int n,m,num,lastans0,u,v,tot,cnt;
struct Edge{int v,next;}E[N1];
int head[N],a[N],b[N],fa[N][32],dep[N];
int rt[M]{0},ls[M]{0},rs[M]{0},siz[M]{0};
void add(int u,int v){E[tot](Edge){v,head[u]};head[u]tot;
}
void modify(int rt,int lastrt,int l,int r,int val){rtcnt;ls[rt]ls[lastrt]; rs[rt]rs[lastrt];siz[rt]siz[lastrt]1;if(lr)return;int midlr1;if(midval)modify(ls[rt],ls[lastrt],l,mid,val);else modify(rs[rt],rs[lastrt],mid1,r,val);
}
int query(int rt1,int rt2,int rt3,int rt4,int l,int r,int k){if(lr)return l;int mid(lr)1;int tmpsiz[ls[rt1]]siz[ls[rt2]]-siz[ls[rt3]]-siz[ls[rt4]];if(tmpk)return query(ls[rt1],ls[rt2],ls[rt3],ls[rt4],l,mid,k);else return query(rs[rt1],rs[rt2],rs[rt3],rs[rt4],mid1,r,k-tmp);
}
void dfs(int u,int f){dep[u]dep[f]1;for(int ihead[u];i;iE[i].next){int vE[i].v;if(vfa[u][0])continue;fa[v][0]u;modify(rt[v],rt[u],1,num,a[v]);dfs(v,u);}
}
int Lca(int x,int y){if(dep[x]dep[y])swap(x,y);int tdep[x]-dep[y];for(int i0;(1i)t;i)if((1i)t)xfa[x][i];for(int i19;i0;i--)if(fa[x][i]!fa[y][i])xfa[x][i],yfa[y][i];if(xy)return x;return fa[x][0];
}
int main(){nread();mread();for(int i1;in;i)b[i]a[i]read();sort(b1,bn1);numunique(b1,bn1)-b;for(int i1;in;i){uread();vread();add(u,v);add(v,u);}for(int i1;in;i)a[i]lower_bound(b1,bnum1,a[i])-b;modify(rt[1],rt[0],1,num,a[1]);dfs(1,0);int uplog2(n);for(int k1;kup;k)for(int i1;in;i)fa[i][k]fa[fa[i][k-1]][k-1];for(int i1;im;i){uread();vread();int kread();u^lastans;int lcaLca(u,v);int ansb[query(rt[u],rt[v],rt[lca],rt[fa[lca][0]],1,num,k)];printf(%d\n,ans);lastansans;}return 0;
}
