强强和萌萌是一对好朋友。有一天他们在外面闲逛，突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了，无数的花瓣以肉眼可见的速度从紫荆树上长了出来。仔细看看的话，这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点。每个节点上有一个可爱的小精灵，新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物，每个小精灵 i 都有一个感受能力值Ri ，小精灵 i, j 成为朋友当且仅当在树上 i 和 j 的距离 dist(i,j) ≤ Ri + R! ，其中 dist(i, j)表示在这个树上从 i 到 j 的唯一路径上所有边的边权和。强强和萌萌很好奇每次新长出一个叶子节点之后，这个树上总共有几对朋友。 

我们假定这个树一开始为空，节点按照加入的顺序从 1开始编号。由于强强非常好奇， 你必须在他每次出现新节点后马上给出总共的朋友对数，不能拖延哦。 

对着题解的指针魔改了一个在洛谷开O2可过，其他网站可过的数组版。

题解请见：

其实理解起来还是很好理解的，关键就在于你的卡常姿势以及代码能力的问题了。

（然而考场谁写谁跪的谁敢写这东西……）

简单叙述题解：

树不会动的时候显然点分治，把条件拆开即可用平衡树维护做（比较基础的点分治，具体做法看参考）。

树会动思考点分治并非一定要重心，只有当差的太离谱时为了效率将点重新变为重心就行。

这就是替罪羊树的思想了：暴力维护，失衡时暴力重建。我们把这样的点所构成的结构叫做点分树。

那最开始的点分树就随便搞，失衡了再静态维护一下即可。

总代码压行后198行……应该不影响阅读，因为linux的问题缩进被吃了一些请见谅。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;typedef long long ll;typedef double dl;const int N=1e5+5;const int mod=1e9;const dl alpha=0.812345;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}inline void put(ll x){ if(x>9)put(x/10); putchar(x%10+48);}struct node{ int to,nxt,w;}e[N*2];int cnt,head[N],r[N],fa[N],size[N],son[N],dis[N],n,q[N];vector
             
              anc[N],id[N],sons[N];bool vis[N];ll ans;int t[40*N][2],s[40*N],p[40*N],w[40*N];int sz,rt[2*N];stack
              
               bin;inline void add(int u,int v,int w){ e[++cnt].to=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;}inline int rand(){ static int seed=233; return seed=(ll)seed*482711%998244353;}inline int f(int x){ return x+n;}inline int getnod(){ if(!bin.empty()){ int u=bin.top();bin.pop(); return u; } return ++sz;}inline void upt(int k){ s[k]=s[t[k][0]]+s[t[k][1]]+1;}inline void zig(int &k){ int y=t[k][0];t[k][0]=t[y][1];t[y][1]=k; s[y]=s[k];upt(k); k=y;}inline void zag(int &k){ int y=t[k][1];t[k][1]=t[y][0];t[y][0]=k; s[y]=s[k];upt(k); k=y;}inline void del(int &k){ if(!k)return; bin.push(k); if(t[k][0])del(t[k][0]); if(t[k][1])del(t[k][1]); k=0;}inline void insert(int &k,int val){ if(!k){ k=getnod();w[k]=val;p[k]=rand(); s[k]=1;t[k][0]=t[k][1]=0; return; } else ++s[k]; if(val<=w[k]){ insert(t[k][0],val); if(p[t[k][0]]
               
                =1;--L){ int u=q[L],v=fa[u]; if(R-size[u]>son[u])son[u]=R-size[u]; if(son[u]
                
                 son[v])son[v]=size[u]; } return g;}inline void dac(int st,int par){ int R=0,g=calcg(st);vis[g]=0; q[++R]=g;fa[g]=0;dis[g]=0; for(int L=1;L<=R;++L){ int u=q[L]; for(int j=head[u];j;j=e[j].nxt){ int v=e[j].to; if(!vis[v]||v==fa[u])continue; fa[v]=u;dis[v]=dis[u]+e[j].w; q[++R]=v; } } for(int L=1;L<=R;++L){ int u=q[L]; id[u].push_back(g); anc[u].push_back(dis[u]); sons[g].push_back(u); insert(rt[g],dis[u]-r[u]); if(par)insert(rt[f(g)],anc[u][anc[u].size()-2]-r[u]); } for(int i=head[g];i;i=e[i].nxt){ int v=e[i].to; if(vis[v])dac(v,g); }}vector
                 
                  tmp;inline void rebuild(int u,int par){ tmp=sons[u]; int len=anc[par].size(); for(int i=0;i
                  
                   alpha*sz_f){ rebuild(id[u][i],(!i)?0:id[u][i-1]); return; } }}inline int solve(int u,int v,int w){ int res=0; anc[u]=anc[v];id[u]=id[v]; anc[u].push_back(-w);id[u].push_back(u); for(int i=0;i