P7537 [COCI2016-2017#4] Rima

非常好的一道题！！！！

字典树上的dp题目

首先建立字典树

开始我理解错了 以为只要树上的1是连续的就满足 于是就打了个56分 树上的最大连续和

出题人还是比较好 这样的情况都有56分 实际情况是

就是从高到低再到高这个情况

问题很明显就变成了维护最大值和次大值（更新最大值的时候一定要先更新次大值）

ans就是 最大＋次大+其他临近节点+本身 （注意这里临近节点是指直接相连的亲儿子！）

dp[u]表示u的子树里面到u的最大值 根节点要特判

只有num[u]！=0 即有以u节点结束的单词才更新dp[u] 因为连续性肯定是要保证的

在每个节点更新ans 不管num[u]是否等于0

比如 hais 和 pais 这两个肯定是成立的 但是num[a]是等于0的

#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=3e6+5;
int tr[maxn][26],dp[maxn],num[maxn];
int n,cnt,ans;
string s,t;
void insert(string ss);
void dfs(int u);
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		t=s;
		int len=s.size();
		for(int j=0;jmax1){
		max2=max1;
		max1=dp[to];
		}
		else if(dp[to]>max2)max2=dp[to];
	}
	if(num[u]){
		if(!res)dp[u]=1;
		else dp[u]=max1+res;
}
	ans=max(ans,max1+max2+num[u]+max(res-2,0));
}