|
t().second);
64 return res;
65 }
66
67 int mid=(l+r)>>1;
68 if (y<=mid) res=min(res,query(p<<1,l,mid,x,y,wei));
69 else if (x>mid) res=min(res,query(p<<1|1,mid+1,r,x,y,wei));
70 else res=min(res,min(query(p<<1,l,mid,x,mid,wei),query(p<<1|1,mid+1,r,mid+1,y,wei)));
71 return res;
72 }
73 int main()
74 {
75 n=read(),L=read();
76 for (int i=1;i<n;i++)
77 a[i].x=read(),a[i].y=read(),a[i].l=read(),b[++num]=a[i].x,b[++num]=a[i].y;
78 sort(b+1,b+num+1);
79 for (int i=1;i<=num;i++)
80 if (b[i]!=b[i-1]) p[b[i]]=++siz;
81 for (int i=1;i<n;i++)
82 a[i].x=p[a[i].x],a[i].y=p[a[i].y];
83
84 ins(1,1,siz,1,siz,make_pair(0,0));
85 for (int i=1;i<n;i++)
86 {
87 f[i]=query(1,1,siz,a[i].x,a[i].y,a[i].l)+1;
88 ins(1,1,siz,a[i].x,a[i].y,make_pair(a[i].l,f[i]));
89 }
90 for (int i=1;i<n;i++)
91 printf("%d\n",f[i]>=n?-1:f[i]);
92 }
|