?

2588: Spoj 10628. Count on a tree

Time Limit: 1 Sec ?

Memory Limit: 256 MB

題目連接

http://www.lydsy.com/JudgeOnline/problem.php?id=2588

Description

給定一棵N個節(jié)點的樹，每個點有一個權(quán)值，對于M個詢問(u,v,k)，你需要回答u xor lastans和v這兩個節(jié)點間第K小的點權(quán)。其中l(wèi)astans是上一個詢問的答案，初始為0，即第一個詢問的u是明文。

Input

第一行兩個整數(shù)N,M。 第二行有N個整數(shù)，其中第i個整數(shù)表示點i的權(quán)值。 后面N-1行每行兩個整數(shù)(x,y)，表示點x到點y有一條邊。 最后M行每行兩個整數(shù)(u,v,k)，表示一組詢問。 ?

Output

M行，表示每個詢問的答案。

Sample Input

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
0 5 2
10 5 3
11 5 4
110 8 2

Sample Output

2
8
9
105
7

HINT

HINT：
N,M<=100000
暴力自重。。。

題意

?

題解：

樹上跑主席樹

這類題都是這樣搞……

代碼來自hzwer:

代碼：

//qscqesze #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <bitset> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define maxn 2000005 #define eps 1e-9 int Num; //const int inf=0x7fffffff; //§&szlig;§é§à§é¨f§3 const int inf=0x3f3f3f3f; inline ll read() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } //************************************************************************************** #define N 100005 #define M 2000005 int n,m,tot,sz,cnt,ind,last; int num[N],pos[N]; int v[N],tmp[N],hash[N],root[N]; int ls[M],rs[M],sum[M]; int deep[N],fa[N][17]; struct data{int to,next;}e[200005];int head[N]; void ins(int u,int v) {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;} void insert(int u,int v) {ins(u,v);ins(v,u);} int find(int x)//二分 {int l=1,r=tot;while(l<=r){int mid=(l+r)>>1;if(hash[mid]<x)l=mid+1;else if(hash[mid]==x)return mid;else r=mid-1;} } void dfs(int x)//lca預處理 {ind++;num[ind]=x;pos[x]=ind;for(int i=1;i<=16;i++)if((1<<i)<=deep[x])fa[x][i]=fa[fa[x][i-1]][i-1];else break;for(int i=head[x];i;i=e[i].next)if(fa[x][0]!=e[i].to){deep[e[i].to]=deep[x]+1;fa[e[i].to][0]=x;dfs(e[i].to);} } int lca(int x,int y)//lca {if(deep[x]<deep[y])swap(x,y);int t=deep[x]-deep[y];for(int i=0;i<=16;i++)if((1<<i)&t)x=fa[x][i];for(int i=16;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];if(x==y)return x;return fa[x][0]; } void update(int l,int r,int x,int &y,int num)//更新 {y=++sz;sum[y]=sum[x]+1;if(l==r)return;ls[y]=ls[x];rs[y]=rs[x];int mid=(l+r)>>1;if(num<=mid)update(l,mid,ls[x],ls[y],num);else update(mid+1,r,rs[x],rs[y],num); } int que(int x,int y,int rk) {int a=x,b=y,c=lca(x,y),d=fa[c][0];a=root[pos[a]],b=root[pos[b]],c=root[pos[c]],d=root[pos[d]];int l=1,r=tot;while(l<r){int mid=(l+r)>>1;int tmp=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];if(tmp>=rk)r=mid,a=ls[a],b=ls[b],c=ls[c],d=ls[d];else rk-=tmp,l=mid+1,a=rs[a],b=rs[b],c=rs[c],d=rs[d];}return hash[l]; } int main() {//freopen("test.txt","r",stdin);n=read(),m=read();for(int i=1;i<=n;i++)v[i]=read(),tmp[i]=v[i];sort(tmp+1,tmp+n+1);hash[++tot]=tmp[1];for(int i=2;i<=n;i++)if(tmp[i]!=tmp[i-1])hash[++tot]=tmp[i];for(int i=1;i<=n;i++)v[i]=find(v[i]);for(int i=1;i<n;i++){int u=read(),v=read();insert(u,v);}dfs(1);for(int i=1;i<=n;i++){int t=num[i];update(1,tot,root[pos[fa[t][0]]],root[i],v[t]);}for(int i=1;i<=m;i++){int x=read(),y=read(),rk=read();x^=last;last=que(x,y,rk);printf("%d",last);if(i!=m)printf("\n");}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/qscqesze/p/4785256.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 2588: Spoj 10628. Count on a tree 树上跑主席树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。