2025-四川省赛-J. Sichuan Provincial Contest · znzryb

## 思路讲解

【【直播回放】VP 四川省赛 2025年06月13日19点场】 【精准空降到 30:57】 [https://www.bilibili.com/video/BV1iXM6zmEXT/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1857](https://www.bilibili.com/video/BV1iXM6zmEXT/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1857)

看哥哥的视频。

主要就是树上dp，维护前缀和后缀。

## AC代码

[https://codeforces.com/group/vXvHT09g9Y/contest/105949/submission/327796835](https://codeforces.com/group/vXvHT09g9Y/contest/105949/submission/327796835)



::: 源代码

```cpp
// Problem: J. Sichuan Provincial Contest
// Contest: Codeforces - The 2025 Sichuan Provincial Collegiate Programming Contest
// URL: https://codeforces.com/group/vXvHT09g9Y/contest/105949/problem/J
// Memory Limit: 256 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;const double pi=acos(-1.0);

ll N,M,Q,X,K,lT;
char S[MAXN];
vector<ll> g[MAXN];		// 记得要清空
string obj="SCCPC";
ll pre[MAXN][6],suf[MAXN][6];
/*

*/
ll ans=0;
void dfs(ll u,ll p){
	if(S[u]==obj[0]){
		pre[u][0]=1;
	}
	if(S[u]==obj[4]){
		suf[u][4]=1;
	}
	FOR(i,0,SZ(g[u])-1){
		ll v=g[u][i];
		if(v==p) continue;
		dfs(v,u);
		FOR(j,0,4){
			ans+=pre[u][j]*suf[v][j+1];
			ans+=suf[u][j]*pre[v][j-1];
		}
		FOR(j,0,4){
			if(S[u]==obj[j]){
				pre[u][j]+=pre[v][j-1];
			}
		}
		FOR(j,0,4){
			if(S[u]==obj[j]){
				suf[u][j]+=suf[v][j+1];
			}
		}
	}
}
inline void init(){
	FOR(i,0,N+5){
		g[i].clear();
	}
	ans=0;
	FOR(i,0,N+5){
		FOR(j,0,5){
			pre[i][j]=0;
			suf[i][j]=0;
		}
	}
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>S[i];
	}
	FOR(i,1,N-1){
		ll u,v;cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(1,1);
// #ifdef LOCAL
    // FOR(i,1,N){
    	// FOR(j,0,4){
    		// cerr<<pre[i][j]<<" ";
    	// }
    	// cerr<<"\n";
    // }
    // cerr<<"\n";
    // FOR(i,1,N){
    	// FOR(j,0,4){
    		// cerr<<suf[i][j]<<" ";
    	// }
    	// cerr<<"\n";
    // }
// #endif
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--)
		solve();
	return 0;
}
/*
AC
https://codeforces.com/group/vXvHT09g9Y/contest/105949/submission/327796835
*/
```


:::


## 心路历程（WA，TLE，MLE……）