Nowcoder 模拟赛 G1T3

2018-09-09 19:32:08


这个题基本是个省选难度

但是现在NOIP越来越毒瘤,搞不好出这样的题(小凯:你是不是看不起我)


首先,对于每一个询问 $u$ ,我们找到它的一个祖先,记为 $p$

这一条路至少要被 $k$ 条给定路径完全覆盖

其实相当于查询在给定的 $m$ 个 $x,y$ 中,有多少个满足

$x$ 在 $u$ 的子树中, $y$ 在 $p$ 的其他子树中或 $p$ 的子树以外

反过来也可以

设 $z$ 为 $lca(x,y)$ ,则路径被划分为 $(x,z)$ 和 $(z,y)$

只需要 $(u,p)$ 被其中一个覆盖即可

只考虑在 $x$ 的子树中的情况

在 $x$ 处放一个 $dep[p]$ 的标记

这样就只需要查询在 $u$ 的子树中有多少标记小于等于 $dep[p]$ 的

可以动态开点线段树, $dfs$ 合并子树信息

查询时可以在线段树上二分,相当于找第 $k$ 小数

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=2e5+5,inf=1e7;
struct node
{
    int to,nxt;
}edge[N<<1];
int n,m,T,num,head[N],f[N][20],dep[N],rt[N];
int cnt,sum[N*80],ls[N*80],rs[N*80];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num]=(node){to,head[from]};
    head[from]=num;
}
void dfs(int k,int fa)
{
    f[k][0]=fa; dep[k]=dep[fa]+1;
    for (reg int i=1;i<=19;i++) f[k][i]=f[f[k][i-1]][i-1];
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v!=fa) dfs(v,k);
    }
}
inline int getlca(int x,int y)
{
    if (dep[x]<dep[y]) swap(x,y);
    for (reg int i=19;~i;i--)
      if (dep[f[x][i]]>=dep[y]) x=f[x][i];
    if (x==y) return x;
    for (reg int i=19;~i;i--)
      if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
void insert(int &now,int l,int r,int x)
{
    if (!now) now=++cnt; ++sum[now];
    if (l==r) return; int mid=(l+r)>>1;
    if (x<=mid) insert(ls[now],l,mid,x);
    else insert(rs[now],mid+1,r,x);
}
int query(int now,int l,int r,int x)
{
    if (sum[now]<x) return inf;
    if (l==r) return l; int mid=(l+r)>>1;
    if (x<=sum[ls[now]]) return query(ls[now],l,mid,x);
    return query(rs[now],mid+1,r,x-sum[ls[now]]);
}
int merge(int a,int b,int l,int r)
{
    if (!a||!b) return a+b; int now;
    sum[now=++cnt]=sum[a]+sum[b];
    if (l==r) return now; int mid=(l+r)>>1;
    ls[now]=merge(ls[a],ls[b],l,mid);
    rs[now]=merge(rs[a],rs[b],mid+1,r);
    return now; 
}
void dfs1(int k,int fa)
{
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==fa) continue; dfs1(v,k);
        rt[k]=merge(rt[k],rt[v],1,n);
    }
}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add_edge(x,y); add_edge(y,x);
    }
    dfs(1,0);
    for (reg int i=1;i<=m;i++)
    {
        int x=read(),y=read(),z=getlca(x,y);
        insert(rt[x],1,n,dep[z]); insert(rt[y],1,n,dep[z]);
    }
    dfs1(1,0); T=read();
    for (reg int i=1;i<=T;i++)
    {
        int x=read(),k=read();
        printf("%d\n",max(0,dep[x]-query(rt[x],1,n,k)));
    }
    return 0;
}