#include <bits/stdc++.h>
#define ll long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e3+5;
vector<pair<int,string>> adj[N];
int diff(string &s1, string &s2){
int cnt = 0;
for(int i = 0;i < s1.size();i++){
if(s1[i]=='@'&&s2[i]!='@') s1[i] = s2[i];
else if(s1[i]!='@'&&s2[i]=='@') s2[i] = s1[i];
else if(s1[i]!=s2[i]) cnt++;
}
return cnt;
}
int ans = 0;
void dfs(int u, string &s){
for(auto &x : adj[u]){
dfs(x.first, x.second);
}
unordered_map<char,int> m;
for(int i = 0;i < s.size();i++){
if(s[i]!='@') continue;
m.clear();
for(auto &x : adj[u]){
if(x.second[i]!='@') m[x.second[i]]++;
}
if(!m.empty()) s[i] = max_element(m.begin(), m.end(), [&](pair<char,int> a, pair<char,int> b){return a.second < b.second;})->first;
}
for(auto &x : adj[u]){
for(int i = 0;i < s.size();i++)
if(x.second[i]=='@') x.second[i] = s[i];
}
}
void dfs2(int u, string &s){
//cout << u << " " << s << "\n";
for(auto &x : adj[u]){
ans += diff(s,x.second);
dfs2(x.first,x.second);
}
}
int main(){
fastio
int n,m;
cin >> n >> m;
string root;
while(n--){
int u,v;
string s;
cin >> u >> v >> s;
if(u==v){
root = s;
continue;
}
adj[v].push_back({u,s});
}
dfs(1,root);
dfs2(1,root);
cout << ans << "\n";
}
創作內容
7/4 APCS
程式 (1)