记录编号	478101	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[WC 2014] 紫荆花之恋	最终得分	100
用户昵称	LadyLex	是否通过	通过
代码语言	C++	运行时间	12.979 s
提交时间	2017-12-08 17:37:51	内存使用	354.86 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define L 1<<20
#define MAXN 100005
#define P 1000000000
#define ll long long
char _buf[L],*S,*T,c; 
const int BufS=3000000,md=1000000000;
char buf[BufS],*inss=buf,*outs=buf,num[10];
inline void pl(register long long a){
    if(!a){*outs++='0',*outs++='\n';return;}
    register int tp=0;while(a)num[tp++]=a%10,a/=10;
    while(tp--)*outs++=num[tp]+'0';*outs++='\n';    
}
#define gc() (S==T&&(T=(S=_buf)+fread(_buf,1,L,stdin),S==T)?0:*S++)
int get()
{
    for(c=gc();c<'0'||c>'9';c=gc());
    int x=c^'0';
    for(c=gc();c>='0'&&c<='9';c=gc())x=x*10+(c^'0');
    return x;
}
struct node{int c[2],s,a;}t[MAXN*200];
bool b[MAXN],bb;
int rx[2],ry[2],lr[2],n,m,i,j,k,l,o,u,v,r[MAXN],f[MAXN],h[MAXN],ne[MAXN<<1],p[MAXN<<1],w[MAXN<<1],s[MAXN],s1[MAXN],in[MAXN],id[MAXN],r1[MAXN],r2[MAXN],d[MAXN],D[MAXN],R[100][MAXN],q[MAXN],pr[MAXN],he,ta,top;
ll ans;
void rot(int &R,bool x)
{
    int y=t[R].c[x];
    t[R].c[x]=t[y].c[!x],t[y].c[!x]=R,t[y].s=t[R].s,
    t[R].s=t[t[R].c[0]].s+t[t[R].c[1]].s+1,R=y;
}
void ins(int &R,int x)
{
    if(!R){R=++top,t[R].s=1,t[R].a=x;return;}
    bool b= x>=t[R].a;
    ins(t[R].c[b],x),t[R].s++;
    if(t[t[R].c[b]].s>t[R].s*.7)rot(R,b);
}
#define del(a) (a=0)
int ask(int R,int x)
{
    if(!R)return 0;
    if(t[R].a>=x)return t[t[R].c[1]].s+1+ask(t[R].c[0],x);
    return ask(t[R].c[1],x);;
}
int bfs(int X,int d1,int d2,int fa)
{
    int i,j,k;
    he=ta=0,D[q[ta++]=X]=d2,pr[X]=0;
    while(he!=ta)
    {
        for(j=h[i=q[he++]],s1[i]=b[i]=1,d[i]=d1+1;j;j=ne[j])if(p[j]!=pr[i]&&d[p[j]]>=d1)D[p[j]]=D[pr[q[ta++]=p[j]]=i]+w[j];
        if(d1)R[d1-1][i]=D[i];
    }
    for(i=ta-1;i>=0;i--)
    {
        s1[k=pr[q[i]]]+=s1[q[i]];
        if(s1[q[i]]<<1>ta)b[k]=0;
        if(s1[q[i]]<<1>=ta&&b[q[i]])break;
    }
    f[j=q[i]]=fa,s[j]=ta;
    if(d[j]=d1)
        in[j]=X,id[j]=d2;
    else in[j]=id[j]=0;
    return j;
}
void dfs(int X)
{
    int i,j,k,l;
    R[d[X]][X]=0,del(r1[X]),ins(r1[X],r[X]);
    for(i=h[X];i;i=ne[i])if(d[p[i]]>=d[X])
    {
        del(r2[j=bfs(p[i],d[X]+1,w[i],X)]);
        for(k=0;k<s[j];k++)
            l=q[k],ins(r1[X],r[l]-D[l]),ins(r2[j],r[l]-D[l]);
        dfs(j);
    }
}
inline void add(int u,int v,int x)
{
    p[++m]=v,ne[m]=h[u],w[m]=x,h[u]=m,
    p[++m]=u,ne[m]=h[v],w[m]=x,h[v]=m;
}
void work(int i)
{
    add(i,f[i],j),d[i]=d[f[i]]+1,s[i]=1,
    in[i]=i,id[i]=j,ins(r1[i],r[i]);
    for(k=0;k<d[i];k++)R[k][i]=R[k][f[i]]+j;
    for(k=d[f[i]],l=f[o=i];l;k--,o=l,l=f[l])
        u=R[k][i]-r[i],ans+=ask(r1[l],u)-ask(r2[o],u);
    for(k=d[f[i]],v=0,l=f[o=i];l;k--,o=l,l=f[l])
    {
        u=r[i]-R[k][i],ins(r1[l],u),ins(r2[o],u),++s[l];
        if(s[l]*0.88<s[o])v=l;
    }
    if(v)
    {
        if(d[v])u=bfs(in[v],d[v],id[v],f[v]);
        else u=bfs(1,0,0,0);
        r2[u]=r2[v],r2[v]=0,dfs(u);
    }
    pl(ans);
}
int main()
{
    freopen("flowera.in","r",stdin);
    freopen("flowera.out","w",stdout);
    get(),n=get(),get(),get();
    r[1]=get(),lr[0]=lr[1]=1,printf("0\n");
    ins(rx[0],r[1]),ins(rx[1],r[1]);
    ins(ry[0],r[1]),ins(ry[1],r[1]);
    for(i=2;i<=n;i++)
    {
        f[i]=get()^ans%P,j=get(),r[i]=get();
        if(f[i]!=lr[0]&&f[i]!=lr[1])break;
        add(i,f[i],j),D[i]=D[f[i]]+j,bb= f[i]==lr[1],lr[bb]=i;
        ans+=ask(rx[bb],D[i]-r[i])+ask(ry[!bb],D[i]-r[i]);
        if(D[i]<=r[1]+r[i])ans--;
        ins(rx[bb],D[i]+r[i]),ins(ry[bb],r[i]-D[i]);
        printf("%lld\n",ans);
    }
    if(i<=n)
    {
        for(k=1;k<=top;k++)t[k].c[0]=t[k].c[1]=0;
        top=0,memset(D,0,sizeof(D)),k=bfs(1,0,0,0),dfs(k);
        for(work(i++);i<=n;i++)
            f[i]=get()^ans%P,j=get(),r[i]=get(),work(i);
    }
    fwrite(buf,1,outs-buf,stdout);
    return 0;
}