题目传送门 solution: 增量构建后缀自动机,对于一个询问串ch,从S(S为初始状态)开始根据trans函数进行转移,ch是原串的一个子串当且仅当转移没有被丢弃。如果被丢弃了,那么答案显然是零,否则假设最后转移到了状态T,那么答案为|endpos(T)|。那么怎么统计每一个节点的|endpos …
BZOJ4736 温暖会指引我们前行

原题链接 http://www.lydsy.com/JudgeOnline/problem.php?id=4736 http://uoj.ac/problem/274 题解 维护关于温度的最大生成树 用LCT来维护 啦啦啦,草率的题解 代码 #include <cstdio> #incl …

题目传送门BZOJ2157 这是一道Link-Cut Tree的模板题,唯一要注意的事情是去相反数以后Min和Max要反过来,还有,点号是从0开始的,但是边号是从1开始的,我被这坑了。。。 #include<stdio.h> #include<algorithm> using …

题目大意 给出一幅无向图,每个点上有两种权值A,B。 求一条1到n的路径,使路径上A的最大值+B的最大值最小。 Solution 如果要使一条路径上一种权值的最大值最小,这条路径一定在这种权值的最小生成树上。但A的最小生成树和B的最小生成树不同,所以不能直接求最小生成树。 而如果我们从小到大枚举一种 …

题目传送门:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1648 将I号点和min(n+1,a[I]+I)连边,这显然是一棵以n+1号点为根的树。于是修改a[I]就相当于修改I的父亲,可以用Link Cut Tree维护 …