strywr

摘要： 重鏈剖分 樹上修改，查詢路徑信息之類的 最多經過logn個輕邊， 這樣可以更好地劃分 注意點: 修改邊權可以轉化到點權上面： 注意lca的位置不要修改， 應該是update(id[y]+1,id[x]) 例題： 輕重邊： https://www.luogu.com.cn/problem/P7735 閱讀全文

摘要： AC自動機 用于多個模式串（模式串在文本串里面出現），和文本串匹配 對模式串建立trie, 每個點上維護一個fail, 每個節點其實代表一個前綴。若干個模式串形成了若干個前綴字符串集合S。fail[i]表示S中的所有字符串中，能和i這個字符串的后綴完全匹配的最長字符串。 (當然這個字符串不能是i本身 閱讀全文