loneliness

题意:

给出一棵以1为根的有向树，每个节点上有一个字符(只会是小写字母)。

多次询问，给出一个字符集合，要求统计树上合法的串的数量。

合法的串满足4个要求:

1.是树上某个点向根方向的走所形成的串

2.串中所有的字符来自给定的字符集合

3.给定的字符集合中的每一个字符都在串中出现过

4.没有被任意一个满足前三条条件的路径完全包含

树的节点数和询问次数均不超过10⁵

分析:

如果一个路径合法的串，当且仅当该路径向两端延伸1个位置都不能有在路径出现的字符。

我们记录每个节点向根方向的最近的出现某个字符的节点，显然合法的串只可能出现在这条路径上。

再记录每个节点所有儿子的字符集合，对于每个节点按深度枚举要走到的字符，判断是否合法。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>inline void Scan(Q&x){
	char c; while(c=g(),c<48||c>57);
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}

#define rep(i,a,b) for(int i=a;i<b;++i)

const int MAXN=50005;
const int Alpha=26;
typedef long long ll;

struct edge{
	int t,n;
	edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
	e[++tot]=edge(t,head[s]),head[s]=tot;
	e[++tot]=edge(s,head[t]),head[t]=tot;
}

char a[MAXN],b[MAXN];

int p[MAXN],dep[MAXN];

int last[MAXN][Alpha];

ll son[MAXN];

void dfs(int x){
	rep(i,0,Alpha)
		last[x][i]=last[p[x]][i];
	last[x][a[p[x]]-'a']=p[x];
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p[x]){
			p[y]=x;
			dep[y]=dep[x]+1;
			son[x]|=1ll<<(a[y]-'a');
			dfs(y);
		}
}

int n,m;

int ans[MAXN];

const int SIZE=(1<<18)-1;
struct hash{
	ll set[MAXN];
	int next[MAXN],id[MAXN];
	int head[SIZE+1],tot;
	inline void insert(ll s,int Id){
		int p=s&SIZE;
		set[++tot]=s,next[tot]=head[p];
		id[tot]=Id,head[p]=tot;
	}
	inline void update(ll s){
		int p=s&SIZE;
		for(int i=head[p];i;i=next[i])
			if(set[i]==s)++ans[id[i]];
	}
}set;

inline bool cmp(int a,int b){return dep[a]>dep[b];}

inline void deal(int x){
	static int q[Alpha+1];
	rep(i,0,Alpha)q[i]=last[x][i];
	sort(q,q+Alpha,cmp);
	ll S=1ll<<(a[x]-'a');
	rep(i,0,Alpha){
		if(S&son[x])break;
		if(!q[i])break;
		ll s=1ll<<(a[q[i]]-'a');
		if(!(S&s)){
			set.update(S);
		}
		S|=s;
	}
	if(S&son[x])return;
	set.update(S);
}

int main(){
	freopen("loneliness.in","r",stdin);
	freopen("loneliness.out","w",stdout);
	Scan(n),Scan(m);
	scanf("%s",a+1);
	rep(i,1,n){
		int u,v;
		Scan(u),Scan(v);
		AddEdge(u,v);
	}
	rep(i,1,m+1){
		ll S=0;
		scanf("%s",b);
		int l=strlen(b);
		rep(j,0,l){
			S|=1ll<<(b[j]-'a');
		}
		set.insert(S,i);
	}
	dep[1]=1,dfs(1);
	rep(i,1,n+1)deal(i);
	rep(i,1,m+1)printf("%d\n",ans[i]);
	return 0;
}