NOIP模拟赛打铁的匠题解

【问题描述】

Mark Douglas是一名优秀的锻造师。与他优秀的锻造水平不相符，他非常穷，以至于很多好刀都因为缺少素材缺少资金无法打造。

Mark把他有能力锻造的所有n种刀建成了一棵锻造树，除了第1种刀可以直接打造以外，其他的刀都只能从某一种刀加工而来。具体而言，第i种刀只能从第fa_i种刀加工而来，花费的费用为w_i，但是第fa_i种刀不能由第i种刀逆加工得到。Mark定义一种刀的价值为利用他现有的刀进行打造的花费。他虽然穷，但是眼光很高，价值低于一定值的刀他都看不上。现在有q次询问，每次询问当Mark手里有第u种刀且他能看上的最小价值为k时，他能看上的所有刀的价值和是多少。

【输入格式】

输入文件名为forging.in。

第一行为一个正整数n。

接下来n-1行，每行两个正整数fa_i w_i。

下一行一个正整数q。

接下来q行，每行两个正整数u k。

【输出格式】

输出文件名为forging.out。

输出q行，每行表示一组询问的答案。

输入：

1 2

1 3

1 2

输出：

【数据范围】

对于1~4号测试点（20%）：1<=n,q<=1000。

对于1~8号测试点（40%）1<=n,q<=100000,1<=k<=50。

对于9~10号测试点（10%）：树的形态为一条链。

对于9~14号测试点（30%）：除1号点外其余所有点的度数不超过2。

对于所有测试点（100%）1<=n,q<=100000,1<=k<=1e9,1<=wi<=1000。

首先这道题，我们可以把它看作主席树裸题，也可以看成线段树合并模板；

然而这里所说的是用分块维护树剖；

一开始我们将这个树进行树链剖分，注意，我们并不用线段树来维护，所以只要把树剖的预处理部分写出来就好了；

我们知道树剖的性质(dfs序当然也可以)：一个以根节点和它的所有子节点所形成的集合是在一段连续的区间；

那么对于每次询问，在每块里二分位置，把每块里大与这个位置的数都累加到答案中；

注意一个细节：当二分的答案是这个区间的最右端时，一定要特判这个点是否满足条件；

时间复杂度时一个O(nlogn+q*sqrt(n)*logn);

可过，不用离线处理，不用离散化，再大的数据范围也可以这么做；

#include <bits/stdc++.h>

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize("Ofast")

#pragma GCC optimize("inline")

#pragma GCC optimize("-fgcse")

#pragma GCC optimize("-fgcse-lm")

#pragma GCC optimize("-fipa-sra")

#pragma GCC optimize("-ftree-pre")

#pragma GCC optimize("-ftree-vrp")

#pragma GCC optimize("-fpeephole2")

#pragma GCC optimize("-ffast-math")

#pragma GCC optimize("-fsched-spec")

#pragma GCC optimize("unroll-loops")

#pragma GCC optimize("-falign-jumps")

#pragma GCC optimize("-falign-loops")

#pragma GCC optimize("-falign-labels")

#pragma GCC optimize("-fdevirtualize")

#pragma GCC optimize("-fcaller-saves")

#pragma GCC optimize("-fcrossjumping")

#pragma GCC optimize("-fthread-jumps")

#pragma GCC optimize("-funroll-loops")

#pragma GCC optimize("-fwhole-program")

#pragma GCC optimize("-freorder-blocks")

#pragma GCC optimize("-fschedule-insns")

#pragma GCC optimize("inline-functions")

#pragma GCC optimize("-ftree-tail-merge")

#pragma GCC optimize("-fschedule-insns2")

#pragma GCC optimize("-fstrict-aliasing")

#pragma GCC optimize("-fstrict-overflow")

#pragma GCC optimize("-falign-functions")

#pragma GCC optimize("-fcse-skip-blocks")

#pragma GCC optimize("-fcse-follow-jumps")

#pragma GCC optimize("-fsched-interblock")

#pragma GCC optimize("-fpartial-inlining")

#pragma GCC optimize("no-stack-protector")

#pragma GCC optimize("-freorder-functions")

#pragma GCC optimize("-findirect-inlining")

#pragma GCC optimize("-frerun-cse-after-loop")

#pragma GCC optimize("inline-small-functions")

#pragma GCC optimize("-finline-small-functions")

#pragma GCC optimize("-ftree-switch-conversion")

#pragma GCC optimize("-foptimize-sibling-calls")

#pragma GCC optimize("-fexpensive-optimizations")

#pragma GCC optimize("-funsafe-loop-optimizations")

#pragma GCC optimize("inline-functions-called-once")

#pragma GCC optimize("-fdelete-null-pointer-checks")

#define inc(i,a,b) for(register int i=a;i<=b;i++)

using namespace std;

int head[200010],cnt;

class littlestar{

    public:

        int to;

        int nxt;

        int w;

        void add(int u,int v,int gg){

            to=v;

            nxt=head[u];

            head[u]=cnt;

            w=gg;

        }

}star[2000010];

int n;

long long val[100010];

int f[100010],top[100010],seg[100010],dep[100010],size[100010],rev[100010],son[100010];

long long b[100010];

void dfs1(int u,int fa)

{

    dep[u]=dep[fa]+1;

    f[u]=fa;

    size[u]=1;

    for(int i=head[u];i;i=star[i].nxt){

        int v=star[i].to;

        if(v==fa) continue;

        dfs1(v,u);

        size[u]+=size[v];

        if(size[v]>size[son[u]]){

            son[u]=v;

        }

    }

}

void dfs2(int u,int fa)

{

    if(son[u]){

        seg[son[u]]=++seg[0];

        rev[seg[0]]=son[u];

        top[son[u]]=top[u];

        dfs2(son[u],u);

    }

    for(int i=head[u];i;i=star[i].nxt){

        int v=star[i].to;

        if(v==fa) continue;

        if(!top[v]){

            seg[v]=++seg[0];

            rev[seg[0]]=v;

            top[v]=v;

            dfs2(v,u);

        }

    }

}

void build()

{

    seg[0]=seg[1]=rev[1]=top[1]=1;

    dfs1(1,0);

    dfs2(1,0);

    inc(i,1,n){

        b[i]=val[rev[i]];

    }

}

void dfs(int u,int fa)

{

    for(register int i=head[u];i;i=star[i].nxt){

        int v=star[i].to;

        if(v==fa) continue;

        val[v]=val[u]+star[i].w;

        dfs(v,u);

    }

}

int num;

int belong[100010],l[100010],r[100010],block;

long long gg[100010];

long long sum[100010];

void build2()

{

    block=sqrt(n);

    num=n/block;

    if(n%block) ++num;

    inc(i,1,n){

        gg[i]=b[i];

        belong[i]=((i-1)/block)+1;

    }

    inc(i,1,num){

        l[i]=block*(i-1)+1;

        r[i]=block*i;

    }

    r[num]=n;

    inc(i,1,num){

        sort(gg+l[i],gg+1+r[i]);

    }

    inc(i,1,n) sum[i]=sum[i-1]+gg[i];

}

long long ans;

inline void query(register int x,register int y,long long goal)

{

    if(belong[x]==belong[y]){

        for(int j=x;j<=y;j++){

            if(b[j]-b[x]>=goal) ans+=(b[j]-b[x]);

        }

        return;

    }

    for(register int i=x;i<=r[belong[x]];i++){

        if(b[i]-b[x]>=goal) ans+=(b[i]-b[x]);

    }

    for(register int i=l[belong[y]];i<=y;i++){

        if(b[i]-b[x]>=goal) ans+=(b[i]-b[x]);

    }

    for(register int i=belong[x]+1;i<=belong[y]-1;i++){

        register int L=l[i],R=r[i],mid;

        while(L<R){

            mid=(L+R)/2;

            if(gg[mid]-b[x]>=goal){

                R=mid;

            }

            else{

                L=mid+1;

            }

        }

        if(L==r[i]){

            if(gg[L]-b[x]>=goal){

                ans+=gg[L]-b[x];

            }

            continue;

        }

        ans+=(sum[r[i]]-sum[L-1]-b[x]*(r[i]-L+1));

    }

}

template<class nT>

inline void read(nT& x)

{

    char c;

    while(c=getchar(),!isdigit(c));

    x=c^48;

    while(c=getchar(),isdigit(c)) x=x*10+c-48;

}

int main()

{

    read(n);

    inc(i,2,n){

        int u,w; scanf("%d%d",&u,&w);

        star[++cnt].add(u,i,w);

    }

    dfs(1,0);

    build();

    build2();

    int q;read(q);

    inc(i,1,q){

        ans=0;

        long long x,goal;

        read(x); read(goal);

        query(seg[x],seg[x]+size[x]-1,goal);

        printf("%lld\n",ans);

    }

}

/*

3

1 2

1 3

2

1 3

1 2

6

1 2

1 2

3 3

3 4

2 5

2

3 2

7

3 1

1 2

3 1

4 2

4 1

4 2

5

*/

巴特西

NOIP模拟赛打铁的匠题解

最新文章

热门文章

巴特西

NOIP模拟赛 打铁的匠 题解

最新文章

热门文章

NOIP模拟赛打铁的匠题解