luogu P6088 [JSOI2015]字符串树 可持久化trie 线段树合并 树链剖分 trie树

标签：line   link   字符   考虑问题   struct   sum   open   const   还需要   

LINK：字符串树

先说比较简单的正解。由于我没有从最简单的考虑答案的角度思考 所以...

下次还需要把所有角度都考察到。

求x~y的答案 考虑 求x_根+y根-2*lca~根的答案。

那么问题变成了 求某个点到根的边有多少条是以当前询问为前缀的。

前缀这个问题容易想到trie树 建立前缀trie树 即 可持久化trie树即可。

还有两种考虑问题的角度。

可以直接对边建立trie树 让询问在上面跑到一个节点 那么 我们问题变成了求某个节点内的终止节点在x~y的路径上的个数。

把点赋上点权 那么树链剖分可以解决 不过线段树则需要先线段树合并一下 复杂度1e6*log+Qlog^2.

代码复杂度较高。

当然还可以离线 考虑对询问建立 trie 拿每一条边在上面跑 最后统计答案和上面的过程差不多。

这里使用的是第一种简便的方法。从某种意义上讲 第一种方法是剩下的方法正难则反的过程。

const int MAXN=100010,N=11;
int n,len=1,id,Q,L;
int lin[MAXN],ver[MAXN>1);
		dfs(tn,x);
	}
}
inline int LCA(int x,int y)
{
	if(d[x]=d[y])x=f[x][i];
	if(x==y)return x;
	fep(Log[d[x]],0,i)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	return f[x][0];
}
inline int ask(int p,int d)
{
	if(!p)return 0;
	if(d==L+1)return sum(p);
	int cc=b[d]-‘a‘;
	return ask(t[p].ch[cc],d+1);
}
int main()
{
	freopen("1.in","r",stdin);
	gt(n);
	rep(2,n,i)
	{
		Log[i]=Log[i>>1]+1;
		int x,y;gt(x);gt(y);
		gc(a[i-1]);add(x,y);add(y,x);
		l[i-1]=strlen(a[i-1]+1);
	}
	dfs(1,0);gt(Q);
	rep(1,Q,i)
	{
		int x,y;
		gt(x);gt(y);gc(b);
		int lca=LCA(x,y);L=strlen(b+1);
		put(ask(root[x],1)+ask(root[y],1)-ask(root[lca],1)*2);
	}
	return 0;
}

luogu P6088 [JSOI2015]字符串树 可持久化trie 线段树合并 树链剖分 trie树

标签：line   link   字符   考虑问题   struct   sum   open   const   还需要   

原文地址：https://www.cnblogs.com/chdy/p/12872001.html