“蔚来杯”2022牛客暑期多校训练营6 B题 Eezie and Pie 树上差分 链序()

 链接:https://ac.nowcoder.com/acm/contest/33191/B来源:牛客网

题目描述

输入描述:

输出描述:

Output NNN integers in a line, the iii-th integer representing the answer for node iii.

输入

10
1 2
2 3
2 4
3 5
4 6
4 7
1 8
8 9
8 10
0 0 1 2 2 5 3 1 0 2

输出

6 6 2 3 1 1 1 2 1 1

分析

用栈存dfs序,记录入栈,出栈的时候删除,保证遍历到当前,栈中存的是该节点的所有祖先。链序

树上差分,遍历到当前节点,可以配送到当前节点 以及 当前节点链上范围d[x] 内的可以配送得到的糕点数增加

最后将求和。太妙了。

//-------------------------代码----------------------------

//#define int ll
const int N = 2e6+10,M = N * 2;
int n,m,d[N],st[N],top,c[N];
V<int> ve[N];

void dfs(int x,int fa) {
    st[++top] = x;
    c[x] ++ ,c[st[top - min(top,d[x] + 1)]]--;
    for(int v:ve[x]) if(v != fa) dfs(v,x);
    top -- ;//
}

void dfss(int x,int fa) {
    for(int v:ve[x]) if(v != fa) {
        dfss(v,x);
        c[x] += c[v];
    }
}


void solve()
{
    cin>>n;assert(1<=n && n <= 2000000);
    fo(i,1,n-1) {
        int x,y;cin>>x>>y;assert(1<=x && x <= n);assert(1<=y && y<= n);
        ve[x].pb(y),ve[y].pb(x);
    }
    fo(i,1,n) {cin>>d[i];assert(0<=d[i] && d[i]<= n);}
    dfs(1,0);
    dfss(1,0);
    fo(i,1,n) cout<<c[i]<<' ';
}

signed main(){
    AC();
    clapping();TLE;
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------
————————

 链接:https://ac.nowcoder.com/acm/contest/33191/B来源:牛客网

题目描述

输入描述:

输出描述:

Output NNN integers in a line, the iii-th integer representing the answer for node iii.

输入

10
1 2
2 3
2 4
3 5
4 6
4 7
1 8
8 9
8 10
0 0 1 2 2 5 3 1 0 2

输出

6 6 2 3 1 1 1 2 1 1

分析

用栈存dfs序,记录入栈,出栈的时候删除,保证遍历到当前,栈中存的是该节点的所有祖先。链序

树上差分,遍历到当前节点,可以配送到当前节点 以及 当前节点链上范围d[x] 内的可以配送得到的糕点数增加

最后将求和。太妙了。

//-------------------------代码----------------------------

//#define int ll
const int N = 2e6+10,M = N * 2;
int n,m,d[N],st[N],top,c[N];
V<int> ve[N];

void dfs(int x,int fa) {
    st[++top] = x;
    c[x] ++ ,c[st[top - min(top,d[x] + 1)]]--;
    for(int v:ve[x]) if(v != fa) dfs(v,x);
    top -- ;//
}

void dfss(int x,int fa) {
    for(int v:ve[x]) if(v != fa) {
        dfss(v,x);
        c[x] += c[v];
    }
}


void solve()
{
    cin>>n;assert(1<=n && n <= 2000000);
    fo(i,1,n-1) {
        int x,y;cin>>x>>y;assert(1<=x && x <= n);assert(1<=y && y<= n);
        ve[x].pb(y),ve[y].pb(x);
    }
    fo(i,1,n) {cin>>d[i];assert(0<=d[i] && d[i]<= n);}
    dfs(1,0);
    dfss(1,0);
    fo(i,1,n) cout<<c[i]<<' ';
}

signed main(){
    AC();
    clapping();TLE;
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------