This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}
const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e9 + 69;
int n, m, u, v, a[maxn], dep[maxn], mx_dep[maxn], res[maxn];
vector<int> g[maxn];
struct ST {
struct node {
int mn, cnt;
friend node operator + (node a, node b) {
if(mini(a.mn, b.mn)) a.cnt = b.cnt;
else if(a.mn == b.mn) a.cnt += b.cnt;
return a;
}
};
node st[4 * maxn];
int lz[4 * maxn];
void fix(int id, int l, int r) {
if(!lz[id]) return;
st[id].mn += lz[id];
if(l != r) {
lz[id << 1] += lz[id];
lz[id << 1 | 1] += lz[id];
}
lz[id] = 0;
}
void build(int id, int l, int r) {
if(l == r) {
st[id] = {0, 1};
return;
}
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = st[id << 1] + st[id << 1 | 1];
}
void update(int id, int l, int r, int u, int v, int val) {
fix(id, l, r);
if(r < u || l > v) return;
if(u <= l && r <= v) {
lz[id] = val;
fix(id, l, r);
return;
}
int mid = l + r >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
st[id] = st[id << 1] + st[id << 1 | 1];
}
node get(int id, int l, int r, int u, int v) {
fix(id, l, r);
if(r < u || l > v) return {oo, 0};
if(u <= l && r <= v) return st[id];
int mid = l + r >> 1;
return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
}
} st;
void dfs(int u, int par) {
mx_dep[u] = 0;
for(auto v:g[u]) {
if(v == par) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
maxi(mx_dep[u], mx_dep[v] + 1);
}
}
void dfs2(int u, int par) {
auto tmp = st.get(1, 1, n, 1, dep[u] - mx_dep[u] - 1);
if(tmp.mn == 0) maxi(res[u], tmp.cnt);
for(auto v:g[u]) {
if(v == par) continue;
st.update(1, 1, n, dep[u] - mx_dep[v] - 1, dep[u] - 1, 1);
}
for(auto v:g[u]) {
if(v == par) continue;
st.update(1, 1, n, dep[u] - mx_dep[v] - 1, dep[u] - 1, -1);
dfs2(v, u);
st.update(1, 1, n, dep[u] - mx_dep[v] - 1, dep[u] - 1, 1);
}
for(auto v:g[u]) {
if(v == par) continue;
st.update(1, 1, n, dep[u] - mx_dep[v] - 1, dep[u] - 1, -1);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen(TASK".inp", "r", stdin);
//freopen(TASK".out", "w", stdout);
cin>>n>>m;
for(int i = 1; i < n; i++) {
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
}
for(int i = 1; i <= n; i++) cin>>a[i];
dep[1] = 1;
dfs(1, 0);
int mx = -1, l = 0;
for(int i = 1; i <= n; i++) {
if(maxi(mx, dep[i])) l = i;
}
dep[l] = 1;
dfs(l, 0);
mx = -1;
int r = 0;
for(int i = 1; i <= n; i++) {
if(maxi(mx, dep[i])) r = i;
}
st.build(1, 1, n);
dep[l] = 1;
dfs(l, 0);
dfs2(l, 0);
dep[r] = 1;
dfs(r, 0);
dfs2(r, 0);
for(int i = 1; i <= n; i++) cout<<min(m, res[i])<<"\n";
return 0;
}
Compilation message (stderr)
joi2019_ho_t5.cpp: In member function 'void ST::build(int, int, int)':
joi2019_ho_t5.cpp:54:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int mid = l + r >> 1;
| ~~^~~
joi2019_ho_t5.cpp: In member function 'void ST::update(int, int, int, int, int, int)':
joi2019_ho_t5.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int mid = l + r >> 1;
| ~~^~~
joi2019_ho_t5.cpp: In member function 'ST::node ST::get(int, int, int, int, int)':
joi2019_ho_t5.cpp:78:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
78 | int mid = l + r >> 1;
| ~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |