#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5000000;
const int N2 = 1e5+5;
vector<array<int, 3>> g[N2];
int ans[N2];
int n, M;
int nxt = 1;
int L[N], R[N], sg[N], lz[N];
vector<array<int, 2>> chsg;
vector<array<int, 2>> chlz;
array<int, 2> push(int u, int l, int r, int U, bool &usedsg, bool &usedlz){
if(lz[u]) {
if(!usedsg){
chsg.push_back({u, sg[u]});
usedsg = true;
}
sg[u] = r-l+1;
}
bool sol = false, sag = false;
if(l != r){
if(L[u]){
chlz.push_back({L[u], lz[L[u]]});
lz[L[u]] += lz[u];
sol = true;
}
if(R[u]){
chlz.push_back({R[u], lz[R[u]]});
lz[R[u]] += lz[u];
sag = true;
}
}
return {sol, sag};
}
void update(int u, int l, int r, int x, int y, int U, bool usedsg, bool usedlz){
auto [sol, sag] = push(u, l, r, U, usedsg, usedlz);
if(y < l or x > r) return;
if(x <= l and y >= r){
if(!usedlz) {
chlz.push_back({u, lz[u]});
usedlz = true;
}
lz[u]++;
auto [sol, sag] = push(u, l, r, U, usedsg, usedlz);
return;
}
///
int m = (l+r)/2;
bool soll = true;
if(y < l or x > m) soll = false;
if(soll){
if(!L[u]) L[u] = ++nxt;
auto [sol, sag] = push(u, l, r, U, usedsg, usedlz);
update(L[u], l, m, x, y, U, false, sol);
} else {
if(L[u]){
auto [sol, sag] = push(L[u], l, m, U, usedsg, usedlz);
}
}
bool sagg = true;
if(y < m+1 or x > r) sagg = false;
if(sagg){
if(!R[u]) R[u] = ++nxt;
auto [sol, sag] = push(u, l, r, U, usedsg, usedlz);
update(R[u], m+1, r, x, y, U, false, sag);
} else {
if(R[u]){
auto [sol, sag] = push(R[u], m+1, r, U, usedsg, usedlz);
}
}
///
if(!usedsg){
chsg.push_back({u, sg[u]});
usedsg = true;
}
sg[u] = sg[L[u]] + sg[R[u]];
if(lz[u]) sg[u] = r-l+1;
}
void dfs(int u, int p, int li, int ri){
chlz.clear(); chsg.clear();
update(1, 1, M, li, ri, u, false, false);
ans[u] = sg[1];
vector<array<int, 2>> chsg2 = chsg;
vector<array<int, 2>> chlz2 = chlz;
for(auto [to, lj, rj]: g[u]){
if(to == p) continue;
dfs(to, u, lj, rj);
}
for(auto [node, ans]: chsg2) sg[node] = ans;
for(auto [node, ans]: chlz2) lz[node] = ans;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> M;
for(int i=1; i<n; i++){
int x, y, li, ri; cin >> x >> y >> li >> ri;
g[x].push_back({y, li, ri});
g[y].push_back({x, li, ri});
}
dfs(1, -1, 0, 0);
for(int i=2; i<=n; i++) cout << ans[i] << '\n';
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |