loj2065 「SDOI2016」模式字符串

ref不是太懂
#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

typedef unsigned long long ull;

int T, n, m, hea[1000005], cnt, uu, vv, rnd[1000005], rot, siz[1000005];

int tot, sf[1000005], sg[1000005], ff[1000005], gg[1000005];

ull bse[1000005], hs1[1000005], hs2[1000005], ans;

char ss[1000005], tt[1000005];

bool vis[1000005];

struct Edge{

	int too, nxt;

}edge[2000005];

void rn(int &x){

	char ch=getchar();

	x = 0;

	while(ch<'0' || ch>'9')	ch = getchar();

	while(ch>='0' && ch<='9'){

		x = x * 10 + ch - '0';

		ch = getchar();

	}

}

void add_edge(int fro, int too){

	edge[++cnt].nxt = hea[fro];

	edge[cnt].too = too;

	hea[fro] = cnt;

}

void getRoot(int x, int f){

	rnd[x] = 0;

	siz[x] = 1;

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(!vis[t] && t!=f){

			getRoot(t, x);

			siz[x] += siz[t];

			rnd[x] = max(rnd[x], siz[t]);

		}

	}

	rnd[x] = max(rnd[x], tot-siz[x]);

	if(rnd[x]<rnd[rot])	rot = x;

}

int dfs(int x, int f, int d, ull hx){

	siz[x] = 1;

	hx = hx * 131 + ss[x];

	if(hs1[d]==hx){

		ff[(d-1)%m+1]++;

		ans += sg[m-(d-1)%m];

	}

	if(hs2[d]==hx){

		gg[(d-1)%m+1]++;

		ans += sf[m-(d-1)%m];

	}

	int tmp=1;

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(!vis[t] && t!=f){

			siz[x] += siz[t];

			tmp = max(tmp, dfs(t, x, d+1, hx)+1);

		}

	}

	return tmp;

}

void work(int x){

	vis[x] = true;

	sf[1] = sg[1] = 1;

	int tmp=0;

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(!vis[t]){

			int k=min(m, dfs(t, x, 2, ss[x])+1);

			tmp = max(tmp, k);

			for(int j=1; j<=k; j++){

				sf[j] += ff[j];

				sg[j] += gg[j];

				ff[j] = gg[j] = 0;

			}

		}

	}

	for(int i=1; i<=tmp; i++)

		sf[i] = sg[i] = 0;

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(!vis[t]){

			rot = 0;

			tot = siz[t];

			getRoot(t, x);

			work(rot);

		}

	}

}

int main(){

	cin>>T;

	while(T--){

		rn(n); rn(m);

		scanf("%s", ss+1);

		memset(hea, 0, sizeof(int)*(n+1));

		memset(vis, 0, sizeof(bool)*(n+1));

		cnt = ans = rot = 0;

		tot = n;

		for(int i=1; i<n; i++){

			rn(uu); rn(vv);

			add_edge(uu, vv);

			add_edge(vv, uu);

		}

		scanf("%s", tt+1);

		bse[0] = 1;

		for(int i=1; i<=n; i++){

			bse[i] = bse[i-1] * 131;

			hs1[i] = hs1[i-1] + tt[(i-1)%m+1] * bse[i-1];

			hs2[i] = hs2[i-1] + tt[m-(i-1)%m] * bse[i-1];

		}

		rnd[0] = 0x3f3f3f3f;

		getRoot(1, 0);

		work(rot);

		printf("%llu\n", ans);

	}

	return 0;

}
巴特西

loj2065 「SDOI2016」模式字符串

最新文章

热门文章
