首先有一个很傻逼的结论：只有叶子节点可能放，证明显然。
所以你把叶子节点全拎出来，二分答案，判断就随一万遍随机顺序放置TPS。然后每次暴力判断就过了。
时间复杂度：$O(Tn^3 \log n)$，但是可以过。

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
#include<bits/stdc++.h>
using namespace std;
vector<int> v[65];
int n,vis[55],one[105],tot,ch[51],g[51][51];
vector<int> d[65];
bool check2(int mid){
    for(int i=1;i<=n;++i)d[i].clear();
    for(int i=1;i<=n;++i){
        for(int j=1;j<=mid;++j){
            d[i].push_back(g[i][ch[j]]);
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            int s=0;
            for(int k=1;k<=mid;++k)
                s+=d[i][k-1]==d[j][k-1];
            if(s==mid)return 0;
        }
    }
    return 1;
}
bool check(int mid){
    for(int i=1;i<=10000;++i){
        memset(vis,0,sizeof vis);
        for(int j=1;j<=mid;++j){
            int t=rand()%tot+1;
            while(vis[t])t=rand()%tot+1;
            ch[j]=one[t];vis[t]=1;
        }
        if(check2(mid))return 1;
    }
    return 0;
}
int main(){
    srand(10007);
    cin>>n;
    if(n==1){
        cout<<"0\n";return 0;
    }
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=n;++i){
        g[i][i]=0;
        for(int j=1;j<=n;++j){
            char c;cin>>c;
            if(c=='Y'){
                v[i].push_back(j);
                g[i][j]=1;
            }
        }
    }
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    for(int i=1;i<=n;++i)
        if(v[i].size()==1)one[++tot]=i;
    int l=1,r=tot;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l<<'\n';
    return 0;
}