G 我的想法是先缩了，统计 $6$ 种剩余字符串（$\texttt{M W MW WM MWM WMW}$），然后大分讨，WA 了

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
	string s;
	cin>>s;
	string x;
	x+=s[0];
	s+='X';
	if(x=="X")x="";
	int top=0;
	int a[6]={};//M W MW WM MWM WMW 
	for(int i=1;i<s.size();i++){
		if(s[i]=='X'){
			if(x.size()==0)continue;
			if(x[0]==x[x.size()-1]){
				if(x[0]=='M'&&x.size()==1)a[0]++;
				else if(x[0]=='M')a[4]++;
				else if(x.size()!=1)a[5]++;
				else a[1]++;
			}else{
				if(x[0]=='M')a[2]++;
				else a[3]++;
			}
			x="";
		}else if(s[i]!=s[i-1])x+=s[i];
	}
	//cout<<a[0]<<' '<<a[1]<<' '<<a[2]<<' '<<a[3]<<' '<<a[4]<<' '<<a[5]<<'\n';
	int flc=min(a[0],a[1]);
	a[0]-=flc;
	a[1]-=flc;
	if(a[0]){
		if(a[5]<a[0]+a[4]||a[5]==a[0]+a[4]&&a[4]==0){
			puts("Water");
			return;
		}else if(a[5]==a[0]+a[4]+1||a[5]==a[0]+a[4]&&a[0]==0){
			puts("Draw");
			return;
		}else{
			puts("Menji");
			return;
		}
	}else if(a[1]){
		a[1]--;
		if(a[1]){
			if(a[4]<a[1]+a[5]||a[4]==a[1]+a[5]&&a[5]==0){
				puts("Water");
			return;
			}else if(a[4]==a[1]+a[5]+1||a[4]==a[1]+a[5]&&a[1]==0){
				puts("Draw");
			return;
			}else{
				puts("Menji");
			return;
			}
		}else{
			if(!a[4]&&!a[5]){
				puts("Menji");
			return;
			}else if(a[4]<a[5]){
				puts("Menji");
			return;
			}else if(a[4]==a[5]+1||a[4]==a[5]){
				puts("Draw");
			return;
			}else{
				puts("Water");
			return;
			}
		}
	}else{
		if(!a[4]&&!a[5]){
			puts("Water");
			return;
		}else if(a[4]>a[5]){
			puts("Water");
			return;
		}else if(a[4]+1==a[5]||a[4]==a[5]){
			puts("Draw");
			return;
		}else{
			puts("Menji");
			return;
		}
	}
}
signed main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}
//MXWWXWWWXMWXMWMMWXMMWMWX

J 我做的树形 dp，设 $dp_{0,i}$ 为第 $i$ 个点不染的情况下使其子树内合法的最少染色数，$dp_{1,i}$ 为第 $i$ 个点染色的情况下使其子树内合法的最少染色数（若为极大值表示不可能），也 WA 了，还被卡常了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[1000005];
int dp[2][1000005],fa[1000005];
vector<int>ve[1000005];
void dfs(int x){
	if(f[x]==1){
		dp[1][x]=10000000000000;
		for(int i=0;i<ve[x].size();i++){
			if(fa[x]==ve[x][i])continue;
			dfs(ve[x][i]);
			dp[0][x]+=min(dp[0][ve[x][i]],dp[1][ve[x][i]]);
		}
		return;
	}
	int flag=10000000000000;
	for(int i=0;i<ve[x].size();i++){
		if(fa[x]==ve[x][i])continue;
		dfs(ve[x][i]);
		flag=min(flag,dp[1][ve[x][i]]-dp[0][ve[x][i]]);
		dp[1][x]+=min(dp[0][ve[x][i]],dp[1][ve[x][i]]);
	}
	if(flag<=0)dp[0][x]=dp[1][x];
	else if(f[x]==2)dp[0][x]=dp[1][x]+flag;
	else dp[0][x]=dp[1][x];
	dp[1][x]++;
	return;
}
void flc(int fath,int x){
	(f[x]==1&&f[fath]==0)?f[fath]=2:1;
	fa[x]=fath;
	for(int i=0;i<ve[x].size();i++){
		if(fath==ve[x][i])continue;
		flc(x,ve[x][i]);
		(f[x]==1&&f[ve[x][i]]==0)?f[ve[x][i]]=2:1;
	}
}
signed main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		int x;
		scanf("%d",&x);
		f[x]=1;
	}
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		ve[u].push_back(v);
		ve[v].push_back(u);
	}
	flc(0,1);
	dfs(1);
	cout<<min(dp[1][1],dp[0][1]);
	return 0;
}

求 hack /kel