3435: [Wc2014]紫荆花之恋
Time Limit: 240 Sec Memory Limit: 512 MB
Submit: 159 Solved: 40
[Submit][Status][Discuss]
Description
强
强和萌萌是一对好朋友。有一天他们在外面闲逛，突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了，无数的花瓣以肉眼可见的速度从紫荆树上长了出来。
仔细看看的话，这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点。每个节点上有一个可爱的小精灵，新长出的节点上也会同时出现一个新的小精
灵。小精灵是很萌但是也很脆弱的生物，每个小精灵 i 都有一个感受能力值Ri ，小精灵 i, j 成为朋友当且仅当在树上 i 和 j 的距离
dist(i,j) ≤ Ri + R! ，其中 dist(i, j)表示在这个树上从 i 到 j
的唯一路径上所有边的边权和。强强和萌萌很好奇每次新长出一个叶子节点之后，这个树上总共有几对朋友。
我们假定这个树一开始为空，节点按照加入的顺序从 1开始编号。由于强强非常好奇， 你必须在他每次出现新节点后马上给出总共的朋友对数，不能拖延哦。
Input
共有 n + 2 行。
第一行包含一个正整数，表示测试点编号。
第二行包含一个正整数 n ，表示总共要加入的节点数。
我们令加入节点前的总共朋友对数是 last_ans，在一开始时它的值为0。
接下来 n 行中第 i 行有三个数 ai, bi, ri，表示节点 i 的父节点的编号为 ai xor (last_ans mod
10^9) (其中xor 表示异或，mod 表示取余，数据保证这样操作后得到的结果介于 1到i – 1之间)，与父节点之间的边权为
ci，节点 i 上小精灵的感受能力值为r!。
注意 a1 = c1 = 0，表示 1 号点是根节点，对于 i > 1，父节点的编号至少为1。
Output
包含 n 行，每行输出1 个整数， 表示加入第 i 个点之后，树上有几对朋友。
Sample Input
0
5
0 0 6
1 2 4
0 9 4
0 5 5
0 2 4
5
0 0 6
1 2 4
0 9 4
0 5 5
0 2 4
Sample Output
0
1
2
4
7
HINT
1<=Ci<=10000
Ai<=2*10^9
Ri<=10^9
N<=100000
本来以这道题的写法我是一定不会写题解的，但是这是我AC400，所以还是记录一下吧。
树的点分治按照归属关系可以建成节点个数n深度log(n)的树，通过在树上维护平衡树来实现点分治，但是本题的加入节点会使整个分治树失衡，所以把他想成是替罪羊树，一旦失衡通过点分治重建整棵子树。
不知道为什么就我一个人有常数问题。各种inline，register，读入优化，for循环合并，平衡树非递归。。。。。╮(╯▽╰)╭整整两天就砸这题里面了。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define MAXN 450000
#define MAXV MAXN
#define MAXE MAXV*2
#define MAXT MAXN*45
#define INF 0x3f3f3f3f
#define alpha 0.90
typedef long long qword;
const int maxbuf=;
char buf[maxbuf*];
char *bufh(buf),*buft(buf+);
#define readbuf\
{\
if ((++bufh)==buft)\
buft=(bufh=buf)+fread(buf,,maxbuf,stdin);\
}
#define nextInt(_r_)\
{\
register int _x_=;\
do\
{\
readbuf;\
}while (*bufh<'' || *bufh>'');\
do\
{\
_x_=_x_*+*bufh-'';\
readbuf;\
}while (*bufh<='' && *bufh>='');\
_r_=_x_;\
}
/*
inline int nextInt()
{
register char ch;
register int x=0;
while (ch=(char)getchar(),ch<'0' || ch>'9');
while (x=x*10+ch-'0',ch=(char)getchar(),ch>='0' && ch<='9');
return x;
}
*/
int pnt[MAXN],rr[MAXN],fdis[MAXN];
int VV[MAXT],S[MAXT],L[MAXT],R[MAXT];
int stack[MAXT];
int tops;
inline void init(int n)
{
tops=-;
int l=min(MAXT,n*);
for (register int i=;i<l;i++)
stack[++tops]=MAXT-i;
return ;
}
inline void update(int now)
{
S[now]=S[L[now]]+S[R[now]]+;
}
inline void r_rotate(int &now)
{
register int t=L[now];
L[now]=R[t];update(now);
R[t]=now;update(t);
now=t;
}
inline void l_rotate(int &now)
{
register int t=R[now];
R[now]=L[t];update(now);
L[t]=now;update(t);
now=t;
}
inline void maintain(int &now)
{
if (S[L[L[now]]]>S[R[now]])
{
r_rotate(now);
// maintain(L[now]);
// maintain(R[now]);
// maintain(now);
}
if (S[R[R[now]]]>S[L[now]])
{
l_rotate(now);
// maintain(L[now]);
// maintain(R[now]);
// maintain(now);
}
if (S[L[R[now]]]>S[L[now]])
{
r_rotate(R[now]);
l_rotate(now);
// maintain(L[now]);
// maintain(R[now]);
// maintain(now);
}
if (S[R[L[now]]]>S[R[now]])
{
l_rotate(L[now]);
r_rotate(now);
// maintain(L[now]);
// maintain(R[now]);
// maintain(now);
}
}
int *st[MAXN];
void Insert(int &now,int v)
{
register int *nn;
register int tops2=-;
if (!now)
{
nn=&now;
}else
{
st[++tops2]=&now;
while (true)
{
if (v<=VV[*st[tops2]])
{
if (!L[*st[tops2]])
{
nn=&L[*st[tops2]];
break;
}
st[tops2+]=&L[*st[tops2]];tops2++;
}
else
{
if (!R[*st[tops2]])
{
nn=&R[*st[tops2]];
break;
}
st[tops2+]=&R[*st[tops2]];tops2++;
}
}
}
*nn=stack[tops--];
if (L[*nn])stack[++tops]=L[*nn];
if (R[*nn])stack[++tops]=R[*nn];
VV[*nn]=v;
S[*nn]=;
L[*nn]=R[*nn]=;
while (~tops2)
{
update(*st[tops2]);
maintain(*st[tops2--]);
}
}
int Get_rank2(register int now,int v)
{
register int ret=;
while (now)
{
if (v<=VV[now])
{
ret+=S[R[now]]+;
now=L[now];
}
else
now=R[now];
}
return ret;
}
void Scan(int &now)
{
if (!now)return ;
Scan(L[now]);
printf("%d ",VV[now]);
Scan(R[now]);
}
struct Edge
{
int np,val;
int lev;
Edge *next,*neg;
}E[MAXE],*V[MAXV];
int tope=-;
inline void addedge(int x,int y,int z)
{
E[++tope].np=y;
E[tope].next=V[x];
E[tope].val=z;
V[x]=&E[tope];
}
int rdis[MAXN],jump[][MAXN];
int depth[MAXN];
inline int lca(int x,int y)
{
if (depth[x]<depth[y])swap(x,y);
int dep=depth[x]-depth[y];
for (register int i=;i<;i++)
if (dep & (<<i))
x=jump[i][x];
if (x==y)return x;
for (register int i=;i>=;i--)
if (jump[i][x]!=jump[i][y])
x=jump[i][x],y=jump[i][y];
return pnt[x];
}
inline int dis(int x,int y)
{
return rdis[x]+rdis[y]-*rdis[lca(x,y)];
}
struct sct_edge
{
sct_edge *next;
int np;
int root;
}sct[MAXN*],*sctv[MAXN];
int topse=-;
int scp[MAXN];
sct_edge* scpe[MAXN];
int scroot[MAXN];
int sctlev[MAXN];
int sctsiz[MAXN];
inline void sct_addedge(int x,int y)
{
sct[++topse].np=y;
sct[topse].next=sctv[x];
sctv[x]=&sct[topse];
}
int q[MAXN];
int pntt[MAXN];
int siz[MAXN];
int find_core(register int now)
{
register int head=-,tail=;
register Edge *ne;
q[]=now;
pntt[now]=now;
while (head<tail)
{
now=q[++head];
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==pntt[now] || ~ne->lev)continue;
q[++tail]=ne->np;
pntt[ne->np]=now;
}
}
int bstsiz=INF,core=-;
for (register int i=tail;i>=;i--)
{
now=q[i];
siz[now]=;
int mxsiz=;
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==pntt[now] || ~ne->lev)continue;
siz[now]+=siz[ne->np];
mxsiz=max(mxsiz,siz[ne->np]);
}
mxsiz=max(mxsiz,(tail+)-siz[now]);
if (bstsiz>mxsiz)
{
bstsiz=mxsiz;
core=now;
}
}
return core;
}
int dstt[MAXN];
void dfs2(register int now,int ds,int p,int &r1,int &r2,int lv)
{
register int head=-,tail=;
register Edge *ne;
q[]=now;
dstt[now]=ds;
pntt[now]=p;
while (head<tail)
{
now=q[++head];
Insert(r1,rr[now]-dstt[now]);
Insert(r2,rr[now]-dstt[now]);
for (ne=V[now];ne;ne=ne->next)
{
if (ne->lev<lv || ne->np==pntt[now])continue;
pntt[ne->np]=now;
q[++tail]=ne->np;
dstt[ne->np]=dstt[now]+ne->val;
} }
}
int solve(int root,int lv)
{
register int core=find_core(root);
register Edge *ne;
sctlev[core]=lv;
Insert(scroot[core],rr[core]-);
sctsiz[core]=siz[root];
if (siz[root]==)
return core;
for (ne=V[core];ne;ne=ne->next)
{
if (~ne->lev)continue;
ne->lev=ne->neg->lev=lv;
int t;
sct_addedge(core,t=solve(ne->np,lv+));
scp[t]=core;
scpe[t]=sctv[core];
dfs2(ne->np,ne->val,core,scpe[t]->root,scroot[core],lv);
}
return core;
}
void sct_rebuild(register int now)
{
int head=-,tail=;
int lv=sctlev[now];
register sct_edge* ns;
register Edge *ne;
q[]=now;
while (head<tail)
{
now=q[++head];
for (ns=sctv[now];ns;ns=ns->next)
q[++tail]=ns->np;
sctv[now]=;
}
head=-,tail=;
now=q[];
pntt[now]=now;
while (head<tail)
{
now=q[++head];
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==pntt[now] || ne->lev<lv)continue;
pntt[ne->np]=now;
ne->lev=ne->neg->lev=-;
q[++tail]=ne->np;
}
}
int pt;
sct_edge *pe;
now=q[];
pe=scpe[now],pt=scp[now];
for (int i=;i<=tail;i++)
{
now=q[i];
if (i && scpe[now]->root)
stack[++tops]=scpe[now]->root;
if (scroot[now])
stack[++tops]=scroot[now];
scroot[now]=;
if (scpe[now])
scpe[now]=NULL;
}
now=solve(now,sctlev[q[]]);
//core->now
if (pe)
pe->np=now;
scpe[now]=pe;
scp[now]=pt;
} int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int x,n;
/*
int root=0;
for (int i=1;i<100;i++)
{
Insert(root,rand()%1000);
Scan(root);printf("\n");
}
return 0;*/
nextInt(x);
qword ans=;
nextInt(n);
init(n);
int rebuild_pos;
for (int i=;i<=n;i++)
{
nextInt(pnt[i]);
nextInt(fdis[i]);
nextInt(rr[i]);
//scanf("%d%d%d",&pnt[i],&fdis[i],&rr[i]);
//printf("%d\n",i);
pnt[i]^=(int)(ans%);
if (i==)
{
scp[i]=;
scpe[i]=NULL;
sctlev[i]=;
Insert(scroot[i],rr[i]-);
sctsiz[i]=;
}else
{
rdis[i]=rdis[pnt[i]]+fdis[i];
depth[i]=depth[pnt[i]]+;
jump[][i]=pnt[i];
for (register int j=;j<;j++)
jump[j][i]=jump[j-][jump[j-][i]];
scp[i]=pnt[i];
sct_addedge(pnt[i],i);
sctlev[i]=sctlev[scp[i]]+;
addedge(pnt[i],i,fdis[i]);
addedge(i,pnt[i],fdis[i]);
V[i]->neg=V[pnt[i]];V[pnt[i]]->neg=V[i];
V[i]->lev=V[pnt[i]]->lev=sctlev[pnt[i]];
scpe[i]=sctv[pnt[i]];
register sct_edge* ns;
sctsiz[i]++;
int d;
rebuild_pos=-;
Insert(scroot[i],rr[i]-);
for (ns=scpe[i],x=scp[i],d=fdis[i];ns;ns=scpe[x],x=scp[x],d=dis(i,x))
{
// printf("[+]");Scan(scroot[x]);printf("\n");
// printf("[-]");Scan(ns->root);printf("\n");
// printf("[F]%d\n",d-rr[i]);
ans+=Get_rank2(scroot[x],d-rr[i])-Get_rank2(ns->root,d-rr[i]);
Insert(scroot[x],rr[i]-d);
Insert(ns->root,rr[i]-d);
sct_edge *ns2;
sctsiz[x]++;
for (ns2=sctv[x];ns2;ns2=ns2->next)
{
if (sctsiz[ns2->np]>sctsiz[x]*alpha)
rebuild_pos=x;
}
}
//sct_rebuild(rand()%i+1);
if (~rebuild_pos)
sct_rebuild(rebuild_pos);
}
printf("%lld\n",ans);
}
}
`