hdu 4117 GRE Words 11年成都现场赛 - c++编程基础

离线建树，然后按顺序把值插入，每插入一个值的时候就按着fail算出该节点的最优解。

一个优化，那些值小于0的节点直接去掉，这个代码不能保证ac，因为这个做法上界很高，但是这题貌似数据随机生成，偶尔能够ac。。。

这个题目正解的话，是要加上线段树来优化这个做法的，因为按照fail指针可以构造出一棵树，算最优解的过程就变成不断更新节点的所有孩子值，求节点的最大值。

#include   
#include   
#include   
#include   
using namespace std;  
const int maxn=3e5+9,N=26,root=0,maxm=2e4+9;  
int cas=0;  
int lon;  
struct  
{  
    int next[N],tmp,fail;  
}trie[290000];  
  
void clr(int t)  
{  
    for(int i=0;i q;  
    q.push(root);  
    while(!q.empty())  
    {  
        int t=q.front();  
        q.pop();  
        for(int i=0;i