生活随笔
收集整理的这篇文章主要介绍了
洛谷P4219 大融合（LCT、虚子树）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
解析
本题需要用LCT维护子树大小
然后我就不会了
然后我就用树剖水过去了
又快又好写，真香
现在详细聊聊如何用LCT维护子树信息
每个结点再定义一个新的变量记录所有虚儿子的信息
然后…完了？
告别盲目pushup，我们来详细聊聊在哪里需要更新虚儿子的信息
毋庸置疑，应该在虚儿子信息改变的时候（废话）
那么什么时候发生改变呢？
access：虚实边会交换状态，需要更新虚子树状态link：增加了虚儿子，需要更新虚子树状态
没了
splay、rotate、makeroot、findroot都是在一个splay里自己玩泥巴，显然不会改变虚儿子的状态
注意cut是减少了一个实儿子，也没有改变虚儿子状态
似乎还不太难对吧
所以，对于LCT的标记问题，我们要理性分析，相信科学
update:
纸上得来终觉浅，绝知此事要躬行
（翻译：不要口胡）
qwq
不自己写一遍是真的找不到坑点…
这里的link改变虚子树状态的时候，会连带上面一串splay的信息都出问题！
而且由于其他地方默认的是原来的信息正确，因此这里即使后面splay或makeroot也于事无补
解决办法是把y转到根再更新其虚子树信息
inline void link(int x
,int y
){makeroot(x
);access(y
);splay(y
);siz0
[y
]+=siz
[x
];f
[x
]=y
;pushup(y
);return;
}
代码
然而懒得重写，还是贴的我的树剖
明天晨练可以写遍这个
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int N
=2e5+100;
const int mod
=1e9+7;
const double eps
=1e-9;
inline ll
read() {ll
x(0),f(1);char c
=getchar();while(!isdigit(c
)){if(c
=='-')f
=-1;c
=getchar();}while(isdigit(c
)){x
=(x
<<1)+(x
<<3)+c
-'0';c
=getchar();}return x
*f
;
}int n
,m
;
struct node{int to
,nxt
;
}p
[N
<<1];
int fi
[N
],cnt
;
inline void addline(int x
,int y
){p
[++cnt
]=(node
){y
,fi
[x
]};fi
[x
]=cnt
;return;
}
struct ope{int op
,x
,y
;
}q
[N
];
struct edge{int x
,y
;
}e
[N
];
int tot
,fa
[N
],num
[N
];
int find(int x
){return x
==fa
[x
]?x
:find(fa
[x
]);}
inline void merge(int x
,int y
){x
=find(x
);y
=find(y
);if(num
[x
]>num
[y
]) swap(x
,y
);e
[++tot
]=(edge
){x
,y
};fa
[x
]=y
;num
[y
]+=num
[x
];return;
}int dfn
[N
],pos
[N
],tim
,f
[N
],siz
[N
],hson
[N
],top
[N
];
int pl
[N
][19];
void dfs1(int x
,int fa
){f
[x
]=fa
;pl
[x
][0]=fa
;for(int k
=1;pl
[x
][k
-1];k
++) pl
[x
][k
]=pl
[pl
[x
][k
-1]][k
-1];siz
[x
]=1;for(int i
=fi
[x
];~i
;i
=p
[i
].nxt
){int to
=p
[i
].to
;if(to
==fa
) continue;dfs1(to
,x
);siz
[x
]+=siz
[to
];if(siz
[to
]>siz
[hson
[x
]]) hson
[x
]=to
;}return;
}
void dfs2(int x
,int tp
){top
[x
]=tp
;pos
[x
]=++tim
;dfn
[tim
]=x
;if(hson
[x
]) dfs2(hson
[x
],tp
);for(int i
=fi
[x
];~i
;i
=p
[i
].nxt
){int to
=p
[i
].to
;if(to
==f
[x
]||to
==hson
[x
]) continue;dfs2(to
,to
);}return;
}int val
[N
];
inline void add(int p
,int w
){for(;p
<=n
;p
+=p
&-p
) val
[p
]+=w
;return;
}
inline int ask(int p
){int res(0);for(;p
;p
-=p
&-p
) res
+=val
[p
];return res
;
}
void init(){for(int i
=1;i
<=n
;i
++){add(pos
[i
],siz
[i
]);add(pos
[i
]+1,-siz
[i
]);}return;
}void upd(int x
,int anc
,int w
){while(top
[x
]!=top
[anc
]){add(pos
[top
[x
]],w
);add(pos
[x
]+1,-w
);x
=f
[top
[x
]];}add(pos
[anc
],w
);add(pos
[x
]+1,-w
);return;
}ll ans
[N
];
int o
;
int main() {
#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);
#endifmemset(fi
,-1,sizeof(fi
));cnt
=-1;n
=read();m
=read();for(int i
=1;i
<=n
;i
++) num
[i
]=1,fa
[i
]=i
;for(int i
=1;i
<=m
;i
++){char c
;int x
,y
;scanf(" %c",&c
);x
=read(),y
=read();q
[i
]=(ope
){c
=='A',x
,y
};if(c
=='A'){addline(x
,y
);addline(y
,x
);merge(x
,y
);}}for(int i
=1;i
<=n
;i
++){if(!siz
[i
]){dfs1(i
,0);dfs2(i
,i
);}}init();for(int i
=m
;i
>=1;i
--){if(q
[i
].op
){int x
=e
[tot
].x
,y
=e
[tot
].y
;--tot
;num
[y
]-=num
[x
];fa
[x
]=x
;x
=q
[i
].x
,y
=q
[i
].y
; if(f
[x
]==y
) swap(x
,y
);int w
=ask(pos
[y
]);int tp
=x
,oo
=find(x
);for(int k
=17;k
>=0;k
--){if(!pl
[tp
][k
]||find(pl
[tp
][k
])!=oo
) continue;tp
=pl
[tp
][k
];}upd(x
,tp
,-w
);}else{int x
=q
[i
].x
,y
=q
[i
].y
;if(f
[x
]==y
) swap(x
,y
);int sum
=num
[find(x
)],bot
=ask(pos
[y
]);ans
[++o
]=1ll*bot
*(sum
-bot
);}}while(o
) printf("%lld\n",ans
[o
--]);return 0;
}
总结
以上是生活随笔为你收集整理的洛谷P4219 大融合（LCT、虚子树）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
