2588: Spoj 10628. Count on a tree
Time Limit: 12 Sec Memory Limit: 128 MBSubmit: 2926 Solved: 667
[Submit][Status][Discuss]
Description
给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。
Input
第一行两个整数N,M。
第二行有N个整数，其中第i个整数表示点i的权值。
后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。
最后M行每行两个整数(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
暴力自重。。。
Source
又一道主席树。
我们把Ti这棵线段树表示i到根节点的线段树，那么Ti可以由Tfa[i]得到，处理好线段树后，就可以解决询问了，对于每个询问u，v，k，只要根据tr[p1].sum+tr[p2].sum-tr[lca].sum-tr[fa[lca]].sum二分答案就可以了。
完美解决。
代码：
#include<cstdio>
#include<algorithm>
#define N 100010
using namespace std;
int n,n1,m,u,v,x,y,k,cnt,edgenum,ans;
int a[N],b[N],vet[2*N],next[2*N],head[N],f[N],d[N],son[N],num[N],top[N],root[N];
struct node{int l,r,sum;}tr[20*N];
void add(int u,int v)
{
edgenum++;
vet[edgenum]=v;
next[edgenum]=head[u];
head[u]=edgenum;
}
void dfs(int u,int fa,int dep)
{
f[u]=fa;
d[u]=dep;
num[u]=1;
int maxnum=0;
for (int e=head[u];e;e=next[e])
{
int v=vet[e];
if (v!=fa)
{
dfs(v,u,dep+1);
num[u]+=num[v];
if (num[v]>maxnum){maxnum=num[v];son[u]=v;}
}
}
}
void dfs(int u,int number)
{
top[u]=number;
if (!son[u]) return;
dfs(son[u],number);
for (int e=head[u];e;e=next[e])
{
int v=vet[e];
if (v!=f[u]&&v!=son[u]) dfs(v,v);
}
}
int lca(int u,int v)
{
while (top[u]!=top[v])
{
if (d[top[u]]<d[top[v]]) swap(u,v);
u=f[top[u]];
}
if (d[u]<d[v]) return u;else return v;
}
void change(int l,int r,int &p,int x)
{
tr[++cnt]=tr[p];p=cnt;tr[p].sum++;
if (l==r) return;
int mid=(l+r)>>1;
if (x<=mid) change(l,mid,tr[p].l,x);else change(mid+1,r,tr[p].r,x);
}
int ask(int x,int y,int k)
{
int p1=root[x],p2=root[y],p3=root[lca(x,y)],p4=root[f[lca(x,y)]];
int l=1,r=n;
while (l<r)
{
int mid=(l+r)>>1;
int t=tr[tr[p1].l].sum+tr[tr[p2].l].sum-tr[tr[p3].l].sum-tr[tr[p4].l].sum;
if (t>=k) {p1=tr[p1].l;p2=tr[p2].l;p3=tr[p3].l;p4=tr[p4].l;r=mid;}else
{p1=tr[p1].r;p2=tr[p2].r;p3=tr[p3].r;p4=tr[p4].r;k-=t;l=mid+1;}
}
return l;
}
void dfs(int u)
{
root[u]=root[f[u]];
change(1,n,root[u],a[u]);
for (int e=head[u];e;e=next[e])
{
int v=vet[e];
if (v!=f[u]) dfs(v);
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
n1=unique(b+1,b+n+1)-b-1;
for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+n1+1,a[i])-b;
for (int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(1,0,1);
dfs(1,1);
dfs(1);
while (m--)
{
scanf("%d%d%d",&x,&y,&k);
ans=b[ask(x^ans,y,k)];
printf("%d",ans);
if (m) printf("\n");
}
}
评论 (0)
