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 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
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 16001000
int n,m;
int ptr[MAXN];
struct Edge
{
int np;
Edge *next;
}E[MAXE],*V[MAXN];
int tope=-;
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+);
}
}
int jump[MAXN][];
void init_lca()
{
int i,j;
for (i=;i<=n;i++)
{
jump[i][]=fa[i];
}
for (j=;j<;j++)
{
for (i=;i<=n;i++)
{
jump[i][j]=jump[jump[i][j-]][j-];
}
}
}
void swim(int &now,int d)
{
int i=;
while (d)
{
if (d&)now=jump[now][i];
i++;
d>>=;
}
}
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=;i>=;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=;
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)/;
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+,r,pos,v);
return ;
}
}
int root[MAXN];
void dfs2(int now)
{
Edge *ne;
add_val(root[now],root[fa[now]],,m,wei[now],);
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=;
scanf("%d%d",&n,&q);
for (i=;i<=n;i++)
{
scanf("%d",&wei2[i].w);
wei2[i].id=i;
}
sort(&wei2[],&wei2[n+],cmp_w);
x=;y=-;
for (i=;i<=n;i++)
{
if (wei2[i].w!=y)
{
y=wei2[i].w;
ptr[x+]=wei2[i].w;
wei2[i].w=++x;
}else wei2[i].w=x;
}
sort(&wei2[],&wei2[n+],cmp_id);
for (i=;i<=n;i++)
wei[i]=wei2[i].w;
for (i=;i<n-;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
Edge *ne;
dfs(,);
init_lca();
//build_tree(root[0],1,m);
add_val(root[],root[],,m,wei[],);
for (ne=V[];ne;ne=ne->next)
dfs2(ne->np);
int t,temp;
int a[],topa;
int ans;
int l,r,mid;
for (i=;i<q;i++)
{
scanf("%d%d%d",&x,&y,&z);
t=lca(x,y);
if (t!=)a[]=root[fa[t]];
else a[]=;
a[]=root[t];
a[]=root[x];
a[]=root[y];
ans=;
l=,r=m;
while (true)
{
mid=(l+r)/;
temp=ans;
if (l==r)break;
if (a[])ans-=tree[tree[a[]].lch].sum;
if (a[])ans-=tree[tree[a[]].lch].sum;
if (a[])ans+=tree[tree[a[]].lch].sum;
if (a[])ans+=tree[tree[a[]].lch].sum;
if (ans>=z)
{
if (a[])a[]=tree[a[]].lch;
if (a[])a[]=tree[a[]].lch;
if (a[])a[]=tree[a[]].lch;
if (a[])a[]=tree[a[]].lch;
r=mid;
ans=temp;
}else
{
if (a[])a[]=tree[a[]].rch;
if (a[])a[]=tree[a[]].rch;
if (a[])a[]=tree[a[]].rch;
if (a[])a[]=tree[a[]].rch;
l=mid+;
}
}
printf("%d\n",ptr[l]);
}
}