此题有SAM的单log做法（小优化）

大体思路同题解区中Cyber_Tree的做法，只不过优化了树上结点对应到相同节点时暴力跳倍增的

\text{log}

，即用先比较深度（长度）再比较原树上

\text{dfn}

序的方法实现排序的

\text{O(1)}

比较。用

\text{dfn}

序是因为若用

vector

存边，则儿子原先就是按编号从小到大排序的（否则再

sort

即可）。

CPP


inline bool rule(int a,int b)
{
    if(pos[a] != pos[b]) return dfn[pos[a]]<dfn[pos[b]];
    if(de[a] != de[b]) return de[a]<de[b];
    return ord[a]<ord[b];//dfn是parent树的dfn序，ord就是原树的
}

此题有SAM的单log做法（小优化）

讨论操作

回复

相关推荐

此题有SAM的单log做法（小优化）