1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 int b[100010];
 5 struct node{int x,y;} a[100010];
 6 int n,m;
 7 
 8 bool cmp(node a,node b)
 9 {
10     return a.x<b.x;
11 }
12 
13 int main()
14 {
15     scanf("%d%d",&n,&m);
16     int ans=n;
17     for (int i=1; i<=m; i++)
18     {
19         scanf("%d%d",&a[i].x,&a[i].y);
20         ans=min(ans,a[i].y-a[i].x+1);
21     }
22     sort(a+1,a+1+m,cmp);
23     for (int i=1; i<=m; i++)
24         a[i].y=a[i].x+ans-1;
25     printf("%d\n",ans);
26     for (int i=1; i<=m; i++)
27     {
28         if (a[i].x==a[i-1].x) continue;
29         if (a[i].x>a[i-1].y)
30         {
31             for (int j=0; j<ans; j++)
32                 b[a[i].x+j]=j;
33         }
34         else {
35             int k=a[i-1].y+1;
36             for (int j=a[i-1].x; j<=a[i].x; j++)
37                 b[k++]=b[j];
38         }
39     }
40     for (int i=1; i<=n; i++) printf("%d ",b[i]);
41 }

 1 #include<bits/stdc++.h>
 2 #define mp make_pair
 3 using namespace std;
 4 typedef long long ll;
 5 struct way{int po,next,len;} e[200010];
 6 int ans[200010],p[200010],a[200010];
 7 ll d[200010];
 8 vector< pair<ll,int> > st;
 9 int n,len;
10 
11 void add(int x,int y,int z)
12 {
13     e[++len].po=y;
14     e[len].next=p[x];
15     e[len].len=z;
16     p[x]=len;
17 }
18 
19 void dfs(int x)
20 {
21     st.push_back(mp(d[x],x));
22     int j=lower_bound(st.begin(),st.end(),mp(d[x]-a[x],0))-st.begin()-1;
23     if (j>=0) ans[st[j].second]--;
24     for (int i=p[x]; i; i=e[i].next)
25     {
26         int y=e[i].po;
27         d[y]=d[x]+e[i].len;
28         dfs(y);
29         ans[x]+=ans[y]+1;
30     }
31     st.pop_back();
32 }
33 
34 int main()
35 {
36     scanf("%d",&n);
37     for (int i=1; i<=n; i++) scanf("%d",&a[i]);
38     for (int i=2; i<=n; i++)
39     {
40         int x,y;
41         scanf("%d%d",&x,&y);
42         add(x,i,y);
43     }
44     dfs(1);
45     for (int i=1; i<=n; i++) printf("%d ",ans[i]);
46 }