首页 > 代码库 > spoj cot: Count on a tree 主席树
spoj cot: Count on a tree 主席树
10628. Count on a tree
Problem code: COT
You are given a tree with N nodes.The tree nodes are numbered from 1 to N.Each node has an integer weight.
We will ask you to perform the following operation:
- u v k : ask for the kth minimum weight on the path from node u to node v
Input
In the first line there are two integers N and M.(N,M<=100000)
In the second line there are N integers.The ith integer denotes the weight of the ith node.
In the next N-1 lines,each line contains two integers u v,which describes an edge (u,v).
In the next M lines,each line contains three integers u v k,which means an operation asking for the kth minimum weight on the path from node u to node v.
Output
For each operation,print its result.
Example
Input:
8 5
8 5105 2 9 3 8 5 7 71 2 1 31 43 53 63 74 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2
Output:2
8
9
105
7
NOI前的最后一道题编这道主席树的题算是了解了对于主席树的“恐惧“。
这道题的大致思路是对于树上每一个点，都在其父节点基础上建主席树。
第一次编没有初始化建树操作的线段树来优化内存。还算比较顺利。以后看题的时候注意对于没有指明范围的量离散化。
虽然参加不了NOI现场赛，但还是希望自己在同步赛中rp++
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define MAXN 211000#define MAXE 211000#define MAXT 16001000int n,m;int ptr[MAXN];struct Edge{ int np; Edge *next;}E[MAXE],*V[MAXN];int tope=-1;void addedge(int x,int y){ E[++tope].np=y; E[tope].next=V[x]; V[x]=&E[tope];}int wei[MAXN];int depth[MAXN];int fa[MAXN];void dfs(int now,int d){ Edge *ne; depth[now]=d; for (ne=V[now];ne;ne=ne->next) { if (ne->np==fa[now])continue; fa[ne->np]=now; dfs(ne->np,d+1); }}int jump[MAXN][20];void init_lca(){ int i,j; for (i=1;i<=n;i++) { jump[i][0]=fa[i]; } for (j=1;j<20;j++) { for (i=1;i<=n;i++) { jump[i][j]=jump[jump[i][j-1]][j-1]; } }}void swim(int &now,int d){ int i=0; while (d) { if (d&1)now=jump[now][i]; i++; d>>=1; }}int lca(int x,int y){ if (depth[x]<depth[y]) { swim(y,depth[y]-depth[x]); } if (depth[y]<depth[x]) { swim(x,depth[x]-depth[y]); } if (x==y)return x; int i; for (i=19;i>=0;i--) { if (jump[x][i]!=jump[y][i]) { x=jump[x][i]; y=jump[y][i]; } } return fa[x];}struct node{ int lch,rch,sum;}tree[MAXT];int topt=0;int get_node(node *nd){ if (nd==NULL) { return ++topt; } topt++; tree[topt]=*nd; return topt;}/*void build_tree(int &now,int l,int r){ now=++topt;// tree[now].l=l;// tree[now].r=r; if (l==r)return ; int mid=(l+r)/2; build_tree(tree[now].lch,l,mid); build_tree(tree[now].rch,mid+1,r);}*/void add_val(int &now,int &base,int l,int r,int pos,int v){ now=get_node(&tree[base]); tree[now].sum+=v; if (l==pos&&r==pos) { return ; } int mid=(l+r)/2; if (pos<=mid) { add_val(tree[now].lch,tree[base].lch,l,mid,pos,v); return ; } if (mid<pos) { add_val(tree[now].rch,tree[base].rch,mid+1,r,pos,v); return ; }}int root[MAXN];void dfs2(int now){ Edge *ne; add_val(root[now],root[fa[now]],1,m,wei[now],1); for (ne=V[now];ne;ne=ne->next) { if (ne->np==fa[now])continue; dfs2(ne->np); }}struct weight_t{ int id,w;}wei2[MAXN];bool cmp_w(const weight_t &w1,const weight_t &w2){ return w1.w<w2.w;}bool cmp_id(const weight_t &w1,const weight_t &w2){ return w1.id<w2.id;}int main(){ //freopen("input.txt","r",stdin); int i,j,k,x,y,z; int q; m=100010; scanf("%d%d",&n,&q); for (i=1;i<=n;i++) { scanf("%d",&wei2[i].w); wei2[i].id=i; } sort(&wei2[1],&wei2[n+1],cmp_w); x=0;y=-1; for (i=1;i<=n;i++) { if (wei2[i].w!=y) { y=wei2[i].w; ptr[x+1]=wei2[i].w; wei2[i].w=++x; }else wei2[i].w=x; } sort(&wei2[1],&wei2[n+1],cmp_id); for (i=1;i<=n;i++) wei[i]=wei2[i].w; for (i=0;i<n-1;i++) { scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } Edge *ne; dfs(1,0); init_lca(); //build_tree(root[0],1,m); add_val(root[1],root[0],1,m,wei[1],1); for (ne=V[1];ne;ne=ne->next) dfs2(ne->np); int t,temp; int a[5],topa; int ans; int l,r,mid; for (i=0;i<q;i++) { scanf("%d%d%d",&x,&y,&z); t=lca(x,y); if (t!=1)a[0]=root[fa[t]]; else a[0]=0; a[1]=root[t]; a[2]=root[x]; a[3]=root[y]; ans=0; l=1,r=m; while (true) { mid=(l+r)/2; temp=ans; if (l==r)break; if (a[0])ans-=tree[tree[a[0]].lch].sum; if (a[1])ans-=tree[tree[a[1]].lch].sum; if (a[2])ans+=tree[tree[a[2]].lch].sum; if (a[3])ans+=tree[tree[a[3]].lch].sum; if (ans>=z) { if (a[0])a[0]=tree[a[0]].lch; if (a[1])a[1]=tree[a[1]].lch; if (a[2])a[2]=tree[a[2]].lch; if (a[3])a[3]=tree[a[3]].lch; r=mid; ans=temp; }else { if (a[0])a[0]=tree[a[0]].rch; if (a[1])a[1]=tree[a[1]].rch; if (a[2])a[2]=tree[a[2]].rch; if (a[3])a[3]=tree[a[3]].rch; l=mid+1; } } printf("%d\n",ptr[l]); }}
spoj cot: Count on a tree 主席树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。