P2922 [USACO08DEC]Secret Message G

字典树很好的一道题

这个题区别于一般的字典树前缀匹配在于

匹配的字符串可能比字典树上的长 也可能比字典树上的短

如果只是维护一个节点会被经过多少次肯定是没法解的

考虑再维护一个endd数组 表示以i节点为结尾的字符串数量

在查找的时候 比匹配字符串短的节点直接+endd数组即可

经过节点数sum就不行 因为我们只找匹配字符这一条线上的 但是sum是维护这个节点以下所有的

比匹配字符长的就可以直接加sum数组就好 这就回到了一般的字典树查找

但是要注意的是要减去endd{root} 因为这个会被加上两次 sum和endd都包含了

#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=5e5+5;
int n,m,cnt;
int tr[maxn][2],sum[maxn],endd[maxn]; 
void insert(string x);
int serach(string x);
int main(){
	cin>>m>>n;
	for(int i=0;i>bi;
		stringstream ss;//黑科技 很好用的
		for(int j=1;j<=bi;j++){
			int xi;cin>>xi;
			ss<>s;
		insert(s);
	}
	for(int i=1;i<=n;i++){
		int bi;cin>>bi;
		stringstream ss;
		for(int j=1;j<=bi;j++){
			int xi;cin>>xi;
			ss<>s;
		cout<