snoi多校シミュレーション試合t 3 z

C Z星(z.pas/c/cpp)
TL:2S  ML:512MB
【Description】
Z星の住民には独特の命名方法がある.Z星では、子供の名前は父の名前で広がっている.拡張とは、父の名前の前と後ろにそれぞれアルファベットを追加することで、追加しなくてもいいです.例えば、父の名前がacであれば、彼の息子の名前はkacshiであってもよく、孫の名前はkacshidashabiであってもよい.
現在、Z星のリーダーの手にはZ星のすべての男性住民の名前表があり、N人です.彼は一部の住民を選んで苦労することを望んでいる.憎しみをできるだけ避けるために、彼は家族を選ぶのに苦労したいと思っています.つまり、表の順番にいくつかの公民を順番に選んで、後の住民がいつも前の住民の息子になるようにしたいと思っています.しかし、彼は名前に特別な趣味を持っていて、彼はすべての住民の名前に採点をして、彼は前の条件を満たす下で、名前の総採点が最も高いことを望んでいます.
【Input】
複数組のテストで、最初の行は整数Tで、データグループ数を表します.
データのセットごとに、最初の行には整数Nがあります.
次にN行、行ごとに文字列と整数があり、男性住民の名前と名前の得点を表す.名前に小文字のアルファベットのみが含まれていることを保証します.
【Output】
合計T行で、行ごとに1つの整数で、最大得点を表します.
【Sample Input】
1
3
ab 2
abd 1
dab 2
【Sample Output】
4
【Hint】
        
30%:N<=500文字列の全長は10000を超えない
100%:N<=20000、文字列の総長は300000を超えず、T<=10、すべての名前の得点の絶対値<=1000.
30-60分:kmp+暴力+負権除去最適化
100分:セグメントツリーfailツリーのdfsシーケンスを維持する
この問題は明らかにまじめにできないので,私たちは逆さまにやった.
セグメントツリーは最大値を維持します.
後から求めた最大値は線分木の点で修正すればよい.
実はacオートマチック+セグメントツリーのテンプレート問題です
詳細とメンテナンス値が多く、下表のポインタが多い.

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int ans,T,n,fail[300005],trie[300005][27],fa[300005],siz,pre[300005],in[300005],out[300005],N,maxx[1200005],dp[300005],a[300005];
char c[300005];
vectore[300005];
queueq;
int read()
{
	int res=0,f=1;
	char c=getchar();
	while(c'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9'){res=res*10+c-'0';c=getchar();}
	return res*f;
}
void insert(int ii)
{
	int len=strlen(c),now=0;
	for(int i=0;i>1;
    if(P<=mid) insert(now<<1,l,mid,P,val);
    else insert(now<<1|1,mid+1,r,P,val);
}
int query(int now,int L,int R,int l,int r)
{
    if(l<=L&&r>=R) return maxx[now];
    int mid=(L+R)>>1;
    return max((l<=mid?query(now<<1,L,mid,l,r):0),(r>mid?query(now<<1|1,mid+1,R,l,r):0));
}
int main()
{
	freopen("z.in","r",stdin);freopen("z.out","w",stdout);
	T=read();
	while(T--)
	{
		siz=N=0;
		for(int i=1;i<=300005;i++) e[i].clear();
        memset(trie,0,sizeof(trie));
      	memset(fail,0,sizeof(fail));
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        memset(maxx,0,sizeof(maxx));
        memset(fa,0,sizeof(fa));
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
		n=read();
		for(int i=1;i<=n;i++)
		{
			scanf("%s",c);
			a[i]=max(read(),0);
			insert(i);
		}	
		buildfail();
		for(int i=1;i<=siz;i++) e[fail[i]].push_back(i);
		dfs(0);
		for(int i=n;i>=1;i--)
		{
			dp[i]=a[i]+query(1,1,N,in[pre[i]],out[pre[i]]);
			int now=pre[i];
			while(now)
			{
				insert(1,1,N,in[now],dp[i]);
				now=fa[now];
			}
			ans=max(ans,dp[i]);
		}
		printf("%d
",ans);
	}
}