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>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const int mxN = (int)1e5+10;
int n, mx, IND = 1;
int segTree[mxN*100], lazy[mxN*100];
vector<pair<int,pair<int,int>>> adj[mxN];
int ans[mxN], root[mxN], L[mxN*100], R[mxN*100];
int newLeaf(int v){ int p = ++IND; segTree[p]=v; return p; }
int newParent(int l, int r){
int p = ++IND; L[p]=l, R[p]=r; lazy[p]=-1;
segTree[p] = segTree[L[p]]+segTree[R[p]];
return p;
}
int newLazyChild(int p, int v, int l, int r){
int ind = ++IND;
L[ind] = L[p];
R[ind] = R[p];
lazy[ind] = v;
segTree[ind] = (r-l+1)*v;
return ind;
}
void prop(int p, int l, int r){
if(!p or l==r or lazy[p]==-1) return;
int mid = (l+r)/2;
if(!L[p]) L[p]=++IND;
if(!R[p]) R[p]=++IND;
L[p] = newLazyChild(L[p],lazy[p],l,mid);
R[p] = newLazyChild(R[p],lazy[p],mid+1,r);
lazy[p]=-1;
}
int upd(int i, int j, int v, int p, int l=1, int r=mx){
if(i>r or j<l or i>j or !p) return p; prop(p,l,r);
if(i<=l and r<=j) return newLazyChild(p,v,l,r);
int mid = (l+r)/2;
if(!L[p] and i<=mid) L[p]=++IND;
if(!R[p] and j>mid) R[p]=++IND;
return newParent(upd(i,j,v,L[p],l,mid),upd(i,j,v,R[p],mid+1,r));
}
int query(int i, int j, int p, int l=1, int r=mx){
if(i>r or j<l or i>j or !p) return 0; prop(p,l,r);
if(i<=l and r<=j) return segTree[p];
int mid = (l+r)/2;
return query(i,j,L[p],l,mid)+query(i,j,R[p],mid+1,r);
}
void dfs(int s, int p){
ans[s] = segTree[root[s]];
for(auto x : adj[s]){
int u = x.fi; if(u==p) continue;
root[u] = upd(x.se.fi,x.se.se,1,root[s]); dfs(u,s);
}
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> mx; root[1] = 1;
memset(lazy,-1,sizeof(lazy));
for(int i = 1; i < n; i++){
int a, b, l, r; cin >> a >> b >> l >> r;
adj[a].pb({b,mp(l,r)}); adj[b].pb({a,mp(l,r)});
}
dfs(1,0);
for(int i = 2; i <= n; i++) cout << ans[i] << "\n";
}
/*
const int mxN = (int)1e5+10;
int n, m, ans[mxN];
vector<pair<int,pair<int,int>>> adj[mxN];
int segTree[mxN*2];
vector<int> lazy(mxN*2, -1);
void prop(int p, int l, int r){
if(l==r or lazy[p]==-1) return;
int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
lazy[p+1] = lazy[rp] = lazy[p]; lazy[p]=-1;
segTree[p+1] = (mid-l+1)*lazy[p+1];
segTree[rp] = (r-mid)*lazy[p+1];
}
void upd(int i, int j, int v, int p=0, int l=1, int r=n){
if(i>r or j<l or i>j) return; prop(p,l,r);
if(i<=l and r<=j){
lazy[p]=v; segTree[p] = (r-l+1)*v;
return;
}
int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
upd(i,j,v,p+1,l,mid), upd(i,j,v,rp,mid+1,r);
segTree[p] = segTree[p+1]+segTree[rp];
}
void dfs(int s, int p){
ans[s] = segTree[0];
for(auto x : adj[s]){
int u = x.fi; if(u==p) continue;
upd(x.se.fi,x.se.se,1); dfs(u,s);
rollback();
}
}
*/
Compilation message (stderr)
Main.cpp: In function 'int upd(int, int, int, int, int, int)':
Main.cpp:42:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
42 | if(i>r or j<l or i>j or !p) return p; prop(p,l,r);
| ^~
Main.cpp:42:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
42 | if(i>r or j<l or i>j or !p) return p; prop(p,l,r);
| ^~~~
Main.cpp: In function 'int query(int, int, int, int, int)':
Main.cpp:51:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
51 | if(i>r or j<l or i>j or !p) return 0; prop(p,l,r);
| ^~
Main.cpp:51:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
51 | if(i>r or j<l or i>j or !p) return 0; prop(p,l,r);
| ^~~~
# | 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... |