前话

史题。

思路分析：

这道题乍一看不好做，于是我们考虑从第二个点入手：如果所有的边双方都可以通过的话，那么必定可以分出胜负。显然，决定两人胜负的就是他们初始的距离的奇偶性。如果双方初始距离为奇数，则 Paula 胜，反之则 Marin 胜。

而这条性质同样适用于其它几个点，但是多了平局的可能。我们将上一个性质判断出来的胜方记作 A，败方记作 B，如果有一条边连接的两个点 B 可以到达但 A 不行，且 A 在 B 到达这两个点之前没有拦住 B 到这两个点的必经之路，那么就会平局。

看着这道题的思路其实并不难，难点在于它的细节是真的多！并且我们还要特判是否有一开始就走不了的情况（光是这个特判就改了一个下午）。

放代码！

代码详解：

#include<bits/stdc++.h>
using namespace std;
#define rint register int
inline int read(){
    int f=0,t=0;
    char c=getchar();
    while(!isdigit(c)) t|=(c=='-'),c=getchar();
    while(isdigit(c)) f=(f<<3)+(f<<1)+c-48,c=getchar();
    return t?-f:f;
}
inline void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar('0'+x%10);
}const int N=1e5+5;
int head[N],to[N<<1],nxt[N<<1],w[N<<1],dep[N][3],cnt,rs,n,a,b;//dep用于计算双方到某个点的距离 
inline void add(int u,int v,int e){nxt[++cnt]=head[u],to[cnt]=v,w[cnt]=e,head[u]=cnt;}
inline void dfs1(int u,int f,int x){
	dep[u][x]=dep[f][x]+1;
	if((x==1&&u==b)||(x==2&&u==a))rs=dep[u][x]; 
	for(rint i=head[u];i;i=nxt[i])
		if(to[i]!=f&&(w[i]&x))
			dfs1(to[i],u,x);
}//dfs1算出双方到每个点的距离
inline int dfs2(int u,int f,int x){
	for(rint i=head[u];i;i=nxt[i]){
		if(to[i]==f||(!(w[i]&x))||(dep[to[i]][x]>=dep[to[i]][((x-1)^1)+1]&&dep[to[i]][((x-1)^1)+1]!=-1))//如果胜方能在败方到达之前到达，则败方不能到达该点
			continue;
		if(dep[to[i]][((x-1)^1)+1]==-1&&dep[u][((x-1)^1)+1]==-1)return 1;//如果一条边的两个端点都符合条件，则判为平局
		if(dfs2(to[i],u,x))return 1;
	}return 0;
}//dfs2判断是否有平局情况
signed main(){
	n=read(),a=read(),b=read();int f1=0,f2=0;
	for(rint i=1;i<n;i++){
		int u=read(),v=read(),e;
		char c=getchar();
		while(c<'a'||c>'z')c=getchar();
		if(c=='p')e=1;
		if(c=='c')e=2;
		if(c=='m')e=3;
		add(u,v,e),add(v,u,e);
		if((a==u||a==v)&&(e!=2)&&b!=u&&b!=v)f1=1;
		if((b==u||b==v)&&(e!=1))f2=1;//特判是否第一步就不能走 
	}if(!f1){
		puts("Marin");
		return 0;
	}if(!f2){
		puts("Paula");
		return 0;
	}memset(dep,-1,sizeof(dep));
	dfs1(a,0,1);dfs1(b,0,2);
	if(dfs2(rs&1?a:b,0,rs&1?1:2)){
		puts("Magenta");
		return 0;
	}if(rs&1)puts("Marin");
	else puts("Paula");
	return 0;
}

后话

一道很好的细节题，使我的大脑旋转。思维难度不高，但是调起来十分困难（最关键是容易虚空调题）。