【[湖南合宿]談笑風生】

2312 ワード

議長の木が板になった
まずこの暴力の異常な問題を見て、この問題をした人は命がないと感じました.
まず(b)が(a)サブツリーの内部にある場合を考えます.このようにすると、サブツリーの内部のすべての深さが(deep[a]+k)に等しい点より小さい貢献がどれだけあるかを知る必要があります.ここの(a,b,c)は同じノードではないので、ここの貢献はサブツリーのサイズが1を減らすことであり、同時に(b)も(a)ではありません.
その後、深さに従って議長ツリーを構築すればいいです.重み値はサブツリーのサイズが1減少するので、サブツリーの内部のすべての距離の点が(k)に等しい点より小さいことによる重み値とをすばやく問い合わせることができます.
その後サブツリーの外部を考えると、(a,b)はすべて(c)の祖先であるため、(b)が(a)サブツリーの内部になければ必ず(a)からルートへの経路上にあり、(c)も(a)のサブツリーでしか選択できないので、重み値は(sum[a]-1)であり、(b)の選択については(a)から上への(k)ノード
コード#コード#
#include
#include
#include
#define re register
#define maxn 300005
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)>1;
    l[root]=build(x,mid);
    r[root]=build(mid+1,y);
    return root;
}
int change(int pre,int x,int y,int pos,LL val)
{
    int root=++cnt;
    d[root]=d[pre]+val;
    if(x==y) return root;
    l[root]=l[pre],r[root]=r[pre];
    int mid=x+y>>1;
    if(pos<=mid) l[root]=change(l[pre],x,mid,pos,val);
    else r[root]=change(r[pre],mid+1,y,pos,val);
    return root;
}
LL query(int pos,int x,int y,int xx,int yy)
{
    if(xx<=x&&yy>=y) return d[pos];
    int mid=x+y>>1;
    if(yy<=mid) return query(l[pos],x,mid,xx,yy);
    if(xx>mid) return query(r[pos],mid+1,y,xx,yy);
    return query(l[pos],x,mid,xx,yy)+query(r[pos],mid+1,y,xx,yy);
}
int head[maxn],deep[maxn],to[maxn],rt[maxn],_to[maxn];
LL p[maxn],sum[maxn];
int n,Q,num,maxdep;
inline void add_edge(int x,int y)
{
    e[++num].v=y;
    e[num].nxt=head[x];
    head[x]=num;
}
inline int read()
{
    char c=getchar();
    int x=0;
    while(c'9') c=getchar();
    while(c>='0'&&c<='9')
      x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x;
}
void dfs(int x)
{
    sum[x]=1;
    to[x]=++tot;
    _to[tot]=x;
    for(re int i=head[x];i;i=e[i].nxt)
    if(!deep[e[i].v])
    {
        deep[e[i].v]=deep[x]+1;
        p[e[i].v]=p[x]+1;
        dfs(e[i].v);
        sum[x]+=sum[e[i].v];
    }
    maxdep=max(maxdep,deep[x]);
}
int main()
{
    n=read();Q=read();
    int x,y;
    for(re int i=1;i