村庄

发表于 更新于 分类于 本文字数： 651 阅读时长 ≈ 2 分钟

题面

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

一个贪心的想法是将连有三个及以上N态点的P态点删去，同时，然后再加上剩下的N态点数就为答案，但贪心做法并不能达到全局最优，如： 

graph TD
1_P-->2_P;
2_P-->3_N;
3_N-->4_P;
3_N-->5_P;
5_P-->6_N;
5_P-->7_N;
4_P-->8_N;
4_P-->9_N;
4_P-->10_N;

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

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

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

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

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

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

于是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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;
}