Codeforces Round #381 (Div. 2) D. Alyona and a tree dfs+二分+线段树延迟操作、树形化线性

Source

Codeforces Round #381 (Div. 2)

My Solution

题意：一颗树，以有向图的方式读入，每个节点都有一个权值，每条边也有一条权值，当u在v的子树中，且u到v的边权和 <= u的点权时称v可以控制u。求出每个点可以控制 的结点的个数。

dfs+二分+线段树延迟操作、树形化线性

线段树延迟操作区间修改单点查询 O(nlogn)

前缀和sum[ptr]维护的是u到根的路径上的边权和 O(n)

用 树形转化为线性的思想 做，dfs到u的子节点v时，用二分的方法找到最靠近根的节点lr， 然后用把[lr, ptr-1]加1。

当当前结点u，开始回溯的时候，此时单点查询，线段树中还维护着的_Query(ptr, ptr)的findans值即为ans[u]。

然后把u在线段树中的值 _Modify(ptr, ptr, - ans[u]) 清零。

复杂度 O(nlogn)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> ii;
const int maxn = 2e5 + 8;

LL pot[4*maxn], lazy[4*maxn];
LL findans;

int sz;

void _Query(int a, int b, int l, int r, int Ind){
    if(a == l && b == r){findans = pot[Ind]; return; }
    int mid = (l + r) >> 1;
    if(lazy[Ind]){
        pot[Ind<<1] += lazy[Ind]; pot[(Ind<<1) + 1] += lazy[Ind];
        lazy[Ind<<1] += lazy[Ind]; lazy[(Ind<<1) + 1] += lazy[Ind]; lazy[Ind] = 0;
    }
    if(a <= mid) { _Query(a, b, l, mid, Ind<<1); } if(b > mid) { _Query(a, b, mid + 1, r, (Ind<<1) + 1); }
}

void _Modify(int a, int b, int l, int r, int Ind, int d){
    if(a <= l && r <= b){pot[Ind] += d; lazy[Ind] += d; return; } int mid = (l + r) >> 1;         //修改的时候不用把lazy传下去
    if(a <= mid){ _Modify(a, b, l, mid, Ind<<1, d); } if(b > mid){ _Modify(a, b, mid + 1, r,(Ind<<1) + 1, d); }
}

inline void Query(int a, int b) {return _Query(a, b, 1, sz, 1);}
inline void Modify(int a,int b,int d){return _Modify(a, b, 1, sz, 1, d);}


LL w[maxn], ans[maxn], sum[maxn];
vector sons[maxn];

inline bool check(const int &ptr, const int &x, const int &v)
{
    if(sum[ptr] - sum[x] <= w[v]) return true;
    else return false;
}

void dfs(int u, int ptr)
{
    if(sons[u].size() == 0) return;
    int sz = sons[u].size(), v, l, r, mid;
    ptr++;
    for(int i = 0; i < sz; i++){
        v = sons[u][i].first;
        sum[ptr] = sons[u][i].second + sum[ptr - 1];
        l = 1, r = ptr;
        while(l + 1 < r){ mid = (l + r) >> 1;
            if(check(ptr, mid, v)) r = mid;
            else l = mid;
        }
        //
        if(check(ptr, l, v) && l < ptr){
            //cout << u << " " << v << endl;
            Modify(l, ptr - 1, 1);
        }
        else if(check(ptr, r, v) && r < ptr){
            //cout << u << " " << v << endl;
            Modify(r, ptr - 1, 1);
        }
        dfs(v, ptr);
        sum[ptr] = 0;

    }
    ptr--;
    Query(ptr, ptr);
    ans[u] = findans;
    //cout << "ans[" << u << "] = " << ans[u] << endl; Modify(ptr, ptr, - ans[u]); } int main() { #ifdef LOCAL freopen("d.txt", "r", stdin); //freopen("d.out", "w", stdout); int T = 2; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); LL n, f, x; cin >> n;
    sz = n;
    for(int i = 1; i <= n; i++){ cin >> w[i];
    }
    for(int i = 2; i <= n; i++){ cin >> f >> x;
        sons[f].push_back(ii(i, x));
    }

    sum[1] = 0;
    dfs(1, 1);
    cout << ans[1];
    for(int i = 2; i <= n; i++){
        cout << " " << ans[i];
    }

    #ifdef LOCAL
    memset(pot, 0, sizeof pot);
    memset(lazy, 0, sizeof lazy);
    for(int i = 1; i <= n; i++) sons[i].clear();
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx