#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define pb push_back
#define se second
#define fi first
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int nax=1e5+5;
struct edge{
int x,l,r;
};
vector<edge> adj[nax];
struct node{
int ans,lazy,cnt,tl,tr,l,r;
node () : ans(0), lazy(0),cnt (0), l(-1), r(-1) {}
};
node segtree[nax*50];
int cnt=1;
int res[nax];
void push_lazy(int pos){
if(segtree[pos].lazy==0) return;
int mid=(segtree[pos].tl+segtree[pos].tr)/2;
if(segtree[pos].l==-1){
segtree[pos].l=cnt++;
segtree[segtree[pos].l].tl=segtree[pos].tl;
segtree[segtree[pos].l].tr=mid;
}
if(segtree[pos].r==-1){
segtree[pos].r=cnt++;
segtree[segtree[pos].r].tl=mid+1;
segtree[segtree[pos].r].tr=segtree[pos].tr;
}
segtree[pos].lazy=0;
}
void update(int pos,int l,int r,int value){
push_lazy(pos);
//cout <<l<<" "<<r<<" "<<pos<<endl;
if(l==segtree[pos].tl&&r==segtree[pos].tr){
segtree[pos].cnt+=value;
if(segtree[pos].cnt) segtree[pos].ans=(segtree[pos].tr-segtree[pos].tl+1);
else segtree[pos].ans=segtree[segtree[pos].l].ans+segtree[segtree[pos].r].ans;
push_lazy(pos);
return;
}
int mid=(segtree[pos].tl+segtree[pos].tr)/2;
//cout <<segtree[pos].tl<<" "<<segtree[pos].tr<<endl;
if(segtree[pos].l==-1){
segtree[pos].l=cnt++;
segtree[segtree[pos].l].tl=segtree[pos].tl;
segtree[segtree[pos].l].tr=mid;
}
if(segtree[pos].r==-1){
segtree[pos].r=cnt++;
segtree[segtree[pos].r].tl=mid+1;
segtree[segtree[pos].r].tr=segtree[pos].tr;
}
if(l>mid) update(segtree[pos].r,l,r,value);
else if(r<=mid) update(segtree[pos].l,l,r,value);
else{
update(segtree[pos].l,l,mid,value);
update(segtree[pos].r,mid+1,r,value);
}
push_lazy(segtree[pos].l);
push_lazy(segtree[pos].r);
//cout <<segtree[pos].tl<<" "<<segtree[pos].tr<<" "<<segtree[segtree[pos].l].ans<<" "<<segtree[segtree[pos].r].cnt<<endl;
segtree[pos].ans=(segtree[pos].cnt ? segtree[pos].tr-segtree[pos].tl+1 : segtree[segtree[pos].l].ans+segtree[segtree[pos].r].ans);
}
void dfs(int x,int p){
res[x]=segtree[0].ans;
for(auto u:adj[x]){
if(p==u.x) continue;
update(0,u.l,u.r,1);
dfs(u.x,x);
update(0,u.l,u.r,-1);
}
return;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
optimise;
int n,m;
cin>>n>>m;
for (int i = 0; i < n-1; ++i)
{
int x,y,l,r;
cin>>x>>y>>l>>r;
x--;y--;
adj[x].pb({y,l,r});
adj[y].pb({x,l,r});
}
segtree[0].tl=0;
segtree[0].tr=1e9;
dfs(0,-1);
for (int i = 1; i < n; ++i)
{
cout <<res[i]<<endl;
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
139608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
139608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
139608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
139608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
139608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
