absi2011's Blog & Daily Life.

一个LCT的模版题

写错了好多次..

感谢@似水流年 翻译..

n个点,要求强制在线(交互):

1(C),连接两点

2(D),删除某两点之间的连边

3(T),问两点是否有边相连

4(E),结束程序

=================

特殊条件:

1,一共会调用n-1次C,这n-1次C好像会把整个图连接成一颗树

题意:

感谢@JCarlson的翻译

给你一个树,点上有权值

你需要....

1,连接x,y这一条边(如果非法输出个-1,成功啥都别输出好了)

2,以x为根,断y和y的父亲(如果非法输出个-1,成功也啥都别输了)

3,x到y的路径上权值+w(非法输出-1,成功不管)

4,询问x到y路径上权值的最大值(非法输出-1,成功输出最大值)

又是一个LCT

写完了以后1A

具体做法有点意思,再写几题把LCT写成模版题即可..

LCT真是麻烦

因为BZOJ挂了,我是在lg上交的

感谢waltz719提供的讲义;感谢wxd,zxx老师提供的书籍