。。。题干中没说如果没有LCA就返回-1啊。。。虽然样例给出了。。

神TM BFS树剖 慢的要死

2000分纪念！！撒花~~

醉了。。。
一上来写二分答案+dfs结果超时2个WA1个
索性把二分答案去了，结果就A了。。。
谁能告诉我为什么？明明剪枝一样多（而且二分答案剪枝减得更多一点点），为什么？？！！

汪汀骗我

1A，好激动~~~

2,3,4没数据啊

看错了n的范围想用线段树优化，写maxn的时候才发现是1e3 - -

十进制快速幂是可以AC的，虽然慢成狗QAQ

身败名裂，没好好读题...............

身败名裂

在BZOJ上RE, 在本OJ AC. 两个OJ的数据应该不一样吧??

VIP a.find(z.top())==string::npos 这个好厉害..学到了...
string::find
Searches the string for the first occurrence of the sequence specified by its arguments.
When pos is specified, the search only includes characters at or after position pos, ignoring any possible occurrences that include characters before pos.
Notice that unlike member find_first_of, whenever more than one character is being searched for, it is not enough that just one of these characters match, but the entire sequence must match.

无聊时自己想了个打印解方法 速度当然没楼上的大神们快- -
深夜又无聊于是乎决定在这里水一贴
用动归的时候已经把每个节点的最大路径值算出来了，
在打印解得时候每次只需要选择比较大的路径值就行（忘了咋推的了 占坑以后补）
从(1,1)开始选择下一行的左边(i+1)(j)或者右边(j+1)(j+1)
比如样例每个状态为
86
57 73
39 46 65
18 27 39 32
12 07 13 24 11
选择的顺序应该是86 73 65 39 24
记录选择的点（用个数组），打印数塔中原来的数据
会发现i是逐层递增的，不需要记录
对于j
d[i+1][j+1]>d[i+1][j]或d[i+1][j+1]<d[i+1][j]
第一种情况时需要把j+1来记录 说明选择的是右边的点 记入数组
第二个则j不需要变 选择的是左边的点 记入数组
打印相应的解就行了

int j=1; now[1]=1; //从点（1,1）开始记录

 for(int i=1;i<=n-1;i++){

 if(d[i+1][j+1]>d[i+1][j]) j++;

 now[m++]=j;

}

for(int i=1;i<=n;i++)

 printf("%d ",a[i][now[i]]);

当初一时兴起想到了一个神奇的压缩trie数占用内存空间的方法。假设trie转移的范围是0~255，这种情况下以直接寻址表的形式跳转的话，也就是每个节点开256个儿子。占用空间极大。
神奇的优化方法:每4位看作一个字符，这样每个节点只需要2^4 = 16个儿子，但是相当于字符串长度 *= 2
这样做可以认为: 时间 *= 2;空间 = 2*sqrt(空间)

场主垃圾线段树板子，常数大如狗。

回复 @mikumikumi :
( 排序之后从小的跑一遍优先解决自己子树的就是最优的了
吐槽: 半个下午.... 把5e4看成了5e5...... M了两次

此题制杖