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

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

### 输出描述:

``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``

### 分析

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

//#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;
}

/*样例区

*/

//------------------------------------------------------------``````
————————

### 输出描述:

``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``

### 分析

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

//#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;
}

/*样例区

*/

//------------------------------------------------------------``````