/* I can do this all day */
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
typedef __int128 INT;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;
template < typename T > using Tree = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, C[N], H[N], dp[N], mark[N], S[N], Ans[N];
set < pii > st;
vector < int > G[N];
void pre(int v, int P = 0)
{
H[v] = H[P] + 1;
dp[v] = 1;
for(auto u : G[v])
{
if(u == P) continue;
pre(u, v);
dp[v] = max(dp[v], dp[u] + 1);
}
}
bool cmp(int i, int j)
{
return dp[i] < dp[j];
}
void dfs(int v, int P, int tp)
{
/*printf("v = %d P = %d\n", v, P);
for(auto x : st)
{
printf("%d %d\n", x.F, x.S);
}
printf("\n");
*/
vector < pii > hist;
sort(all(G[v]), cmp);
int Mx1 = 0, Mx2 = 0, id1 = -1;
for(auto u : G[v])
{
if(u == P) continue;
if(dp[u] > Mx1)
{
Mx2 = Mx1;
Mx1 = dp[u];
id1 = u;
}
else if(dp[u] > Mx2)
{
Mx2 = dp[u];
}
}
while(SZ(st))
{
pii cu = *st.begin();
cu.F = -cu.F;
if(cu.F >= H[v] - Mx1)
{
hist.push_back(cu);
st.erase(st.begin());
mark[cu.S] = 0;
}
else
{
break;
}
}
/*printf("Mx1 = %d Mx2 = %d after : \n", Mx1, Mx2);
for(auto x : st)
{
printf("%d %d\n", x.F, x.S);
}
printf("\n");
*/
if(S[v] == tp) Ans[v] += SZ(st);
if(!mark[C[v]])
{
mark[C[v]] = 1;
st.insert({-H[v], C[v]});
}
for(auto u : G[v])
{
if(u == P || u == id1) continue;
dfs(u, v, tp);
}
if(st.count({-H[v], C[v]}))
{
st.erase({-H[v], C[v]});
mark[C[v]] = 0;
}
while(SZ(hist))
{
pii cu = hist.back();
if(cu.F >= H[v] - Mx2)
{
break;
}
mark[cu.S] = 1;
st.insert({-cu.F, cu.S});
hist.pop_back();
}
if(!mark[C[v]])
{
mark[C[v]] = 1;
st.insert({-H[v], C[v]});
}
if(id1 != -1)
{
dfs(id1, v, tp);
}
if(st.count({-H[v], C[v]}))
{
st.erase({-H[v], C[v]});
mark[C[v]] = 0;
}
}
int fir[N], sec[N];
int main()
{
fast_io;
cin >> n >> m;
for(int i = 1; i < n; i ++)
{
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
for(int i = 1; i <= n; i ++)
{
cin >> C[i];
}
pre(1, 0);
int L = 0, R = 0;
for(int i = 1; i <= n; i ++)
{
if(H[i] > H[L]) L = i;
}
pre(L, 0);
///printf("L = %d\n", L);
for(int i = 1; i <= n; i ++)
{
fir[i] = H[i];
if(H[i] > H[R]) R = i;
///printf("i = %d H = %d dp = %d\n", i, H[i], dp[i]);
}
pre(R, 0);
for(int i = 1; i <= n; i ++)
{
sec[i] = H[i];
if(fir[i] > sec[i])
{
S[i] = 0;
}
else
{
S[i] = 1;
}
}
pre(L, 0);
///printf("R = %d\n", R);
dfs(L, 0, 0);
st.clear();
memset(mark, 0, sizeof mark);
pre(R, 0);
for(int i = 1; i <= n; i ++)
{
///printf("i = %d H = %d dp = %d\n", i, H[i], dp[i]);
}
dfs(R, 0, 1);
for(int i = 1; i <= n; i ++)
{
cout << Ans[i] << "\n";
}
return 0;
}
/* check corner case(n = 1?), watch for negetive index or overflow */
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
27724 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
27920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
157 ms |
36568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
338 ms |
40368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
27724 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
27920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
