# _使用 $\color{Red} \mid\text{markdown}$_ 以获得 $\color{Green} \mid\text{更好的}$ 阅读体验
by twelveZ @ 2018-08-04 11:15:21
```cpp
include<iostream>
include<cstdio>
include<cstdlib>
include<cstring>
include<string>
include<cmath>
include<algorithm>
define inf 2100000000
define ll long long
define mod 1000000000
define N 100010
define D 120
using namespace std; int cyc,n,cnt,top,qu[ND],po[N],pre[N];ll ans; int q[N],w[N],size[N],fa[N],flag[N],check[N],bel[N][D]; int k,la[N],ff[N2],dis[N][D],s[N],sze[N],d[N]; struct node{int a,b,c;}map[N2]; struct info{int c[2],fa,val,size,cnt,key;}t[ND];
void adde(int a,int b,int c) { map[++k]=(node){a,b,c};ff[k]=la[a];la[a]=k; map[++k]=(node){b,a,c};ff[k]=la[b];la[b]=k; }
class trape { int newnode() { int res; if(top)res=qu[top--]; else res=++cnt; t[res].key=t[res].fa=t[res].c[0]=t[res].c[1]=0; t[res].val=-inf;t[res].size=t[res].cnt=0; return res; } void update(int x) { int lc=t[x].c[0],rc=t[x].c[1]; t[x].size=t[lc].size+t[x].cnt+t[rc].size; } void rotate(int x,int k) { int y=t[x].fa,f=(t[t[y].fa].c[1]==y); if(y==rt)rt=x; t[x].fa=t[y].fa;t[t[x].fa].c[f]=x; t[y].c[k]=t[x].c[k^1];t[t[y].c[k]].fa=y; t[x].c[k^1]=y;t[y].fa=x; update(y);update(x); } void insert(int x,int val) { if(!t[x].cnt)t[x].val=val,t[x].key=rand(); if(val==t[x].val){t[x].cnt++;t[x].size++;return;} if(val<t[x].val) { if(!t[x].c[0])t[t[x].c[0]=newnode()].fa=x; insert(t[x].c[0],val); if(t[x].key<t[t[x].c[0]].key) rotate(t[x].c[0],0); } else { if(!t[x].c[1])t[t[x].c[1]=newnode()].fa=x; insert(t[x].c[1],val); if(t[x].key<t[t[x].c[1]].key) rotate(t[x].c[1],1); } update(x); } int qry(int x,int val) { if(!x)return 0; int lc=t[x].c[0],rc=t[x].c[1]; if(t[x].val<val)return qry(rc,val); if(t[x].val==val)return t[x].cnt+t[rc].size; return qry(lc,val)+t[x].cnt+t[rc].size; } void erase(int x) { if(!x)return;qu[++top]=x; int lc=t[x].c[0],rc=t[x].c[1]; erase(lc);erase(rc); } public: int rt; void insert(int val){insert(rt,val);} int qry(int val){return qry(rt,val);} void clear(){erase(rt);rt=newnode();} }T1[N],T2[N];
int find(int S) { int l=1,r=2,res,minn=inf;q[1]=S;flag[S]=1; while(l<r) { int x=q[l++];size[x]=1;w[x]=0; for(int a=la[x];a;a=ff[a]) if(!check[map[a].b]&&!flag[map[a].b]) q[r]=map[a].b,fa[q[r]]=x,flag[q[r]]=1,r++; } for(int i=r-1;i;i--) { int x=q[i];flag[x]=0; size[fa[x]]+=size[x]; w[fa[x]]=max(w[fa[x]],size[x]); int num=max(w[x],r-size[x]-1); if(num<minn)minn=num,res=x; } return res; }
void bfs(int S,int dep) { int l=1,r=2;q[1]=S;dis[S][dep]=0;flag[S]=1; while(l<r) { int x=q[l++];bel[x][dep]=S; T1[S].insert(s[x]-dis[x][dep]); if(dep-1)T2[S].insert(s[x]-dis[x][dep-1]); for(int a=la[x];a;a=ff[a]) if(!check[map[a].b]&&!flag[map[a].b]) { q[r]=map[a].b;flag[q[r]]=1; dis[q[r]][dep]=dis[x][dep]+map[a].c;r++; } } for(int i=r-1;i;i--)flag[q[i]]=0;sze[S]=r-1; }
int build(int x,int dep,int pr) { x=find(x);check[x]=1; pre[x]=pr;bfs(x,d[x]=dep); for(int i=dep+1;bel[x][i];i++)bel[x][i]=0; for(int a=la[x];a;a=ff[a]) if(!check[map[a].b])build(map[a].b,dep+1,x); return x; }
void dfs(int x,int dep,int S) { check[x]=pre[x]=d[x]=sze[x]=0; T1[x].clear();T2[x].clear(); for(int a=la[x];a;a=ff[a]) if(bel[map[a].b][dep]==S&&check[map[a].b]) dfs(map[a].b,dep,S); }
void rebuild(int x) { int pr=pre[x],de=d[x]; dfs(x,de,x);build(x,de,pr); }
void add(int x,int b,int c) { int tot=0;pre[x]=b;d[x]=d[b]+1;check[x]=1; T1[x].clear();T2[x].clear(); for(int i=x,pr=0;i;pr=i,i=pre[i]) { if(i!=x)dis[x][d[i]]=dis[b][d[i]]+c; ans+=T1[i].qry(dis[x][d[i]]-s[x]); if(pr)ans-=T2[pr].qry(dis[x][d[i]]-s[x]); po[++tot]=i;sze[i]++;bel[x][d[i]]=i; } for(int i=1;i<=tot;i++) { T1[po[i]].insert(s[x]-dis[x][d[po[i]]]); if(i<tot)T2[po[i]].insert(s[x]-dis[x][d[po[i+1]]]); } for(int i=tot;i>1;i--) if(sze[po[i-1]]>sze[po[i]]*0.88) {rebuild(po[i]);return;} }
void prework() { t[0].size=t[0].cnt=t[0].key=0; t[0].c[0]=t[0].c[1]=t[0].fa=0; t[0].val=-inf; }
int get(int x){return x^(ans%mod);} int main() { int a,c; scanf("%d%d",&cyc,&n);prework(); for(int i=1;i<=n;i++) { scanf("%d%d%d",&a,&c,&s[i]); if(a=get(a))adde(i,a,c); add(i,a,c);printf("%lld\n",ans); } return 0; }
```
by twelveZ @ 2018-08-04 11:15:53
使用Dev-C++的AStyle功能获得更好的体验。
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define inf 2100000000
#define ll long long
#define mod 1000000000
#define N 100010
#define D 120
using namespace std;
int cyc,n,cnt,top,qu[ND],po[N],pre[N];
ll ans;
int q[N],w[N],size[N],fa[N],flag[N],check[N],bel[N][D];
int k,la[N],ff[N2],dis[N][D],s[N],sze[N],d[N];
struct node {
int a,b,c;
} map[N2];
struct info {
int c[2],fa,val,size,cnt,key;
} t[ND];
void adde(int a,int b,int c) {
map[++k]=(node) {
a,b,c
};
ff[k]=la[a];
la[a]=k;
map[++k]=(node) {
b,a,c
};
ff[k]=la[b];
la[b]=k;
}
class trape {
int newnode() {
int res;
if(top)res=qu[top--];
else res=++cnt;
t[res].key=t[res].fa=t[res].c[0]=t[res].c[1]=0;
t[res].val=-inf;
t[res].size=t[res].cnt=0;
return res;
} void update(int x) {
int lc=t[x].c[0],rc=t[x].c[1];
t[x].size=t[lc].size+t[x].cnt+t[rc].size;
} void rotate(int x,int k) {
int y=t[x].fa,f=(t[t[y].fa].c[1]==y);
if(y==rt)rt=x;
t[x].fa=t[y].fa;
t[t[x].fa].c[f]=x;
t[y].c[k]=t[x].c[k^1];
t[t[y].c[k]].fa=y;
t[x].c[k^1]=y;
t[y].fa=x;
update(y);
update(x);
} void insert(int x,int val) {
if(!t[x].cnt)t[x].val=val,t[x].key=rand();
if(val==t[x].val) {
t[x].cnt++;
t[x].size++;
return;
}
if(val<t[x].val) {
if(!t[x].c[0])t[t[x].c[0]=newnode()].fa=x;
insert(t[x].c[0],val);
if(t[x].key<t[t[x].c[0]].key) rotate(t[x].c[0],0);
} else {
if(!t[x].c[1])t[t[x].c[1]=newnode()].fa=x;
insert(t[x].c[1],val);
if(t[x].key<t[t[x].c[1]].key) rotate(t[x].c[1],1);
}
update(x);
} int qry(int x,int val) {
if(!x)return 0;
int lc=t[x].c[0],rc=t[x].c[1];
if(t[x].val<val)return qry(rc,val);
if(t[x].val==val)return t[x].cnt+t[rc].size;
return qry(lc,val)+t[x].cnt+t[rc].size;
} void erase(int x) {
if(!x)return;
qu[++top]=x;
int lc=t[x].c[0],rc=t[x].c[1];
erase(lc);
erase(rc);
} public:
int rt;
void insert(int val) {
insert(rt,val);
} int qry(int val) {
return qry(rt,val);
} void clear() {
erase(rt);
rt=newnode();
}
} T1[N],T2[N];
int find(int S) {
int l=1,r=2,res,minn=inf;
q[1]=S;
flag[S]=1;
while(l<r) {
int x=q[l++];
size[x]=1;
w[x]=0;
for(int a=la[x]; a; a=ff[a]) if(!check[map[a].b]&&!flag[map[a].b]) q[r]=map[a].b,fa[q[r]]=x,flag[q[r]]=1,r++;
}
for(int i=r-1; i; i--) {
int x=q[i];
flag[x]=0;
size[fa[x]]+=size[x];
w[fa[x]]=max(w[fa[x]],size[x]);
int num=max(w[x],r-size[x]-1);
if(num<minn)minn=num,res=x;
}
return res;
}
void bfs(int S,int dep) {
int l=1,r=2;
q[1]=S;
dis[S][dep]=0;
flag[S]=1;
while(l<r) {
int x=q[l++];
bel[x][dep]=S;
T1[S].insert(s[x]-dis[x][dep]);
if(dep-1)T2[S].insert(s[x]-dis[x][dep-1]);
for(int a=la[x]; a; a=ff[a]) if(!check[map[a].b]&&!flag[map[a].b]) {
q[r]=map[a].b;
flag[q[r]]=1;
dis[q[r]][dep]=dis[x][dep]+map[a].c;
r++;
}
}
for(int i=r-1; i; i--)flag[q[i]]=0;
sze[S]=r-1;
}
int build(int x,int dep,int pr) {
x=find(x);
check[x]=1;
pre[x]=pr;
bfs(x,d[x]=dep);
for(int i=dep+1; bel[x][i]; i++)bel[x][i]=0;
for(int a=la[x]; a; a=ff[a]) if(!check[map[a].b])build(map[a].b,dep+1,x);
return x;
}
void dfs(int x,int dep,int S) {
check[x]=pre[x]=d[x]=sze[x]=0;
T1[x].clear();
T2[x].clear();
for(int a=la[x]; a; a=ff[a]) if(bel[map[a].b][dep]==S&&check[map[a].b]) dfs(map[a].b,dep,S);
}
void rebuild(int x) {
int pr=pre[x],de=d[x];
dfs(x,de,x);
build(x,de,pr);
}
void add(int x,int b,int c) {
int tot=0;
pre[x]=b;
d[x]=d[b]+1;
check[x]=1;
T1[x].clear();
T2[x].clear();
for(int i=x,pr=0; i; pr=i,i=pre[i]) {
if(i!=x)dis[x][d[i]]=dis[b][d[i]]+c;
ans+=T1[i].qry(dis[x][d[i]]-s[x]);
if(pr)ans-=T2[pr].qry(dis[x][d[i]]-s[x]);
po[++tot]=i;
sze[i]++;
bel[x][d[i]]=i;
}
for(int i=1; i<=tot; i++) {
T1[po[i]].insert(s[x]-dis[x][d[po[i]]]);
if(i<tot)T2[po[i]].insert(s[x]-dis[x][d[po[i+1]]]);
}
for(int i=tot; i>1; i--) if(sze[po[i-1]]>sze[po[i]]*0.88) {
rebuild(po[i]);
return;
}
}
void prework() {
t[0].size=t[0].cnt=t[0].key=0;
t[0].c[0]=t[0].c[1]=t[0].fa=0;
t[0].val=-inf;
}
int get(int x) {
return x^(ans%mod);
}
int main() {
int a,c;
scanf("%d%d",&cyc,&n);
prework();
for(int i=1; i<=n; i++) {
scanf("%d%d%d",&a,&c,&s[i]);
if(a=get(a))adde(i,a,c);
add(i,a,c);
printf("%lld\n",ans);
}
return 0;
}
```
by agicy @ 2018-08-04 11:45:28