首页 > 代码库 > Spoj 10628. Count on a tree
Spoj 10628. Count on a tree
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
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
8
9
105
7
HINT
HINT：
N,M<=100000
暴力自重。。。
Source
鸣谢seter
思路
树链剖分+主席树，然后用一棵线段树辅助查询。
代码实现
#include<cstdio>const int maxn=1e5+10;inline int min_(int x,int y){return x<y?x:y;}inline int max_(int x,int y){return x>y?x:y;}int h[maxn],hs,et[maxn<<1],en[maxn<<1];int p[maxn],pf[maxn],pd[maxn],pt[maxn],pp[maxn],pps,psz[maxn],pws[maxn];int s[maxn],ss;int rt[maxn],t[maxn<<4],ft[maxn<<4];int n,m;int a,b,c,ans;void dfs1(int k,int f,int d){ pf[k]=f,pd[k]=d,psz[k]=1; for(int i=h[k];i;i=en[i]) if(et[i]!=f){ dfs1(et[i],k,d+1); psz[k]+=psz[et[i]]; if(psz[et[i]]>psz[pws[k]]) pws[k]=et[i]; }}void dfs2(int k,int t){ s[++pps]=p[k],pp[k]=pps; if(pws[k]) dfs2(pws[k],t); for(int i=h[k];i;i=en[i]) if(et[i]!=pf[k]&&et[i]!=pws[k]) dfs2(et[i],et[i]);}void build(int k,int l,int r){ if(l==r){ t[k]=s[++ss]; return; } int t}void clear(){ }int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&p[i]); for(int i=1;i<n;i++){ scanf("%d%d",&a,&b); ++hs,et[hs]=b,en[hs]=h[a],h[a]=hs; ++hs,et[hs]=a,en[hs]=h[b],h[b]=hs; } dfs1(1,1,1); dfs2(1,1); for(int i=1;i<=m;i++){ scanf("%d%d%d",&a,&b,&c);a^=ans; clear(); printf("%d\n",ans); } return 0;}
Spoj 10628. Count on a tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。