村庄

首先想到将各个联通块缩成一个点来解决问题，接下来就是考虑将各个联通块经过变换都变为P态：

贪心做法为4，而正解应该为3

那么我们接下来应该考虑的是每次操作的影响，对于每次操作，都会使该块与相邻联通块合成一个新的整体，所以约束条件应该转到联通块树的最长路径也即树的直径，这样的话。树直径上的点全转为P态时，其余树干的点也均转为P态

而对于树的直径，我们可以两遍dfs来求，参考：树的直径

于是考虑答案的组成情况：

1.路径长度为奇数，即有偶数个点，那么答案便是

2.路径长度为偶数，即有奇数个点，那么我们就需要判断树直径终点或端点状态来加1

于是：

const int N = 2e5 + 86;
vector<char> c(N);
bitset<489899> np;
struct No
{
    int to, nxt;
} e[N * 4];
int hd[N*2], tot = 1, cnt = 1, vis[N];
inline void add(int x, int y)
{
    e[++tot] = (No){y, hd[x]};
    hd[x] = tot;
    e[++tot] = (No){x, hd[y]};
    hd[y] = tot;
}

void dfs(int a, int ma)
{
    vis[a] = ma;
    for (int eg = hd[a]; eg; eg = e[eg].nxt)
    {
        if (!vis[e[eg].to] && c[e[eg].to] == c[a])
            dfs(e[eg].to, ma);
    }
}

LL n,max1,dis[N*4],u,v;

void dfss(int now,int fat)
{
    dis[now] = dis[fat] + 1;
    for(int i = hd[now]; i; i = e[i].nxt)
      if(e[i].to != fat) dfss(e[i].to,now);
}
void get_road(int st)
{
    dis[0]=-1;
    dfss(st,0);
    for(int i = n+5, maxdis = 0; i <= cnt-1; i ++)
      if(dis[i] > maxdis) u = i,maxdis = dis[i];
    dfss(u,0);
    for(int i = n+5, maxdis = 0; i <= cnt-1; i ++)
      if(dis[i] > maxdis) v = i,maxdis = dis[i];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    f(i, 1, n) cin >> c[i];
    cnt+=n+4;
    f(i, 1, n - 1)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
    }
    f(i, 1, n)
    {
        if (!vis[i])
        {
            dfs(i, cnt++);
            np[vis[i]]=(c[i]=='P');
        }
    }
    map<LL ,map<LL,int> >tr;
    f(i, 1, n)
    {
        for (int eg = hd[i]; eg; eg = e[eg].nxt)
        {
            if (vis[i] != vis[e[eg].to]&&!tr[min(vis[i],vis[e[eg].to])][max(vis[i],vis[e[eg].to])])
            {
                tr[min(vis[i],vis[e[eg].to])][max(vis[i],vis[e[eg].to])]=1;
                add(vis[i],vis[e[eg].to]);
            }
        }
    }
    get_road(vis[1]);
    if(dis[v]&1){
        cout<<((dis[v]+1)>>1);
    }
    else cout<<((dis[v])>>1)+(1^np[v]);
    return 0;
}