CF1714G 题解

· · 题解

题外话：

感谢这道题把我送到了 1606th，并助我上了 pupil。

题意

定义 r_i 如下：
从 1 点到 i 点路径上，最多前 r_i 条边上的 b 总和不大于 1 到 i 路径上每一条边的 a 总和。

求 r_2,r_3,\cdots,r_n。

做法

既然需要用到总和，那么记录一下前缀和就行了。

显然，前缀和数组是递增的，也就是说，将对于每个点 i，在 1 点到 i 点路径上的前缀和数组二分，就能求出 r_i

至于怎么求，dfs 到一个点的时候，就顺便记录从 1 点 到这个点路径上的 a 前缀和，以及 b 的前缀和，这个可以从父节点递推出来。

不过直接这么递推，记录的不是同一条路径上的前缀和。

处理方法（或者说具体实现）是，维护一个 top，代表前缀和数组的顶部，当搜到一个点时，top 加一，代表当前路径加上了一个点，同时记录前缀和；当退出当前点时，将 top 减一，代表当前路径不再包含该点。

剩余的看代码注释吧。

Code

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const int maxn=2e5+5;
    int t;
    int head[maxn];
    struct EDGE
    {
        int to,nxt,a,b;
    }edge[maxn<<1];
    int cnt;
    inline void add(int u,int to,int a,int b)
    {
        edge[++cnt].to=to;
        edge[cnt].a=a;
        edge[cnt].b=b;
        edge[cnt].nxt=head[u];
        head[u]=cnt;
    }
    int n;
    ll qzh[maxn];
    int top;
    ll qzh2[maxn];
    int r[maxn];
    void dfs(int u,int giva,int givb,int _fa)
    {
        top++;//当前路径的前缀和数组增加一个元素
        qzh[top]=qzh[top-1]+(ll)giva;//记录 1---->u 的 a 前缀和
        qzh2[top]=qzh2[top-1]+(ll)givb;//记录 1----->u 的 b 前缀和
        int pos=upper_bound(qzh2+1,qzh2+top+1,qzh[top])-qzh2;
        //二分求出第一个 b 前缀和大于 1---->u 的 a 前缀和的点（第一个不符合要求的点）
        //这个点在路径上的编号减去 1 就是最后一个符合要求的点。
        if(pos==top+1)
        {//如果所有的点都符合要求，那就输出这条路径点的总量-1，就是 1----> u 的边的数量
            r[u]=top-1;
        }
        if(pos!=top+1)
        {//如果不是所有的点都符合要求
            r[u]=pos-2;//pos-1是最后一个符合要求的点，而 1---->(pos-1)，有 pos-2 条边。
        }
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(to==_fa)continue;
            dfs(to,edge[i].a,edge[i].b,u);
        }
        top--;//退出当前点，当前路径不再包含该点
    }
    void main()
    {
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            for(int i=2;i<=n;i++)
            {
                int p,a,b;
                scanf("%d%d%d",&p,&a,&b);
                add(i,p,a,b);
                add(p,i,a,b);
            }
            dfs(1,0,0,0);
            for(int i=2;i<=n;i++)
            {
                printf("%d ",r[i]);
            }
            printf("\n");
            //清空数据
            cnt=0;
            for(int i=0;i<=n;i++)
            {
                head[i]=0;
            }
        }
    }
}
int main()
{
    Main::main();
    return 0;
}