Subtask 1

- Một đỉnh không thể là gốc khi và chỉ khi mà hai cạnh xuất phát từ nó có ký tự giống nhau.

- Vì thế, ta có thể xét từng đỉnh rồi đếm.

- Độ phức tạp ~O(N)~

Subtask 2

- Ta sẽ xét mọi đỉnh là gốc rồi thực hiện DFS để xem rằng đỉnh có thỏa mãn hay không.

- Để xem rằng có câu lặp lại hay không thì ta có thể sử dụng Trie để kiểm tra.

- Độ phức tạp ~O(N^2)~

Subtask 3

- Ta thầy là nếu có đỉnh ~A~ sao cho có hai đỉnh ~B~ và ~C~ nối với ~A~ và cạnh ~AB~ và cạnh ~BC~ có cùng ký tự thì chắc chắn đáp án chỉ có thể nằm trong cây con có gốc ~B~ hoặc ~C~.

- Chứng minh: Xét các đỉnh không nằm trong cây con có gốc là ~B~ hoặc ~C~. Gọi đỉnh ta đang xét là ~D~. Vì đồ thị là cây nên chỉ có một đường đi ~D~ đến ~A~. Nếu ta đi từ ~D~ đến ~B~ thì xâu có được là (xâu đi từ ~D~ đến ~A~)+(ký tự trên cạnh ~AB~). Nếu ta đi từ ~D~ đến ~C~ thì xâu ta có được là (xâu đi từ ~D~ đến ~A~)+(ký tự trên cạnh ~AC~). Mà ta thấy là (xâu từ ~D~ đến ~A~) giống nhau, ký tự trên cạnh ~AC~ và ký tự trên cạnh ~AB~ giống nhau nên hai xâu từ ~DB~ và ~DC~ giống nhau nên các đỉnh ~D~ không thỏa mãn.

- Từ điều chứng minh trên, ta dễ dàng nhận xét rằng là nếu một đỉnh có số cạnh nối với nó lớn hơn 3 thì chắc chắn đáp án là 0 do phần giao của các cây con thỏa mãn không thể lớn hơn ~0~.

- Ngoài ra, các đỉnh có đúng ~3~ cạnh nói với nó thì chắc chắn chúng phải có quan hệ là cha con của nhau. Nếu chúng không phải cha con của nhau thì phần giao của chúng sẽ là ~0~. Vì thế ta chỉ cần xét các đỉnh có số cạnh nối với nó là ~3~, xét xem chúng có phải cha con của nhau không rồi ta sẽ xét xem bọn chúng có phải cha con của nhau không. Đáp án sẽ là kích cỡ cây con của đỉnh có 3 cạnh nối với nó thấp nhất trừ đi 1.

- vấn đề cuối cùng của subtask này là tìm gốc của cây để có thể dựng LCA cho dễ. ta xét hàm dfs trên cây thông thường. Bình thường, ta sẽ đưa vào hai tham số là ~u~ (đỉnh hiện tại) và ~par~ là cha của nó. Ta sẽ chọn một đỉnh bất kỳ làm gốc trước. Nếu ta gặp một đỉnh có 3 cạnh nối. Nếu cạnh nối từ ~u~ đến ~par~ có ký tự khác hai cạnh còn lại thì ta chắc chắn sẽ không dfs tiếp xuống đỉnh đó đó do nếu ta dfs xuống đỉnh đó thì khi ta xây dựng LCA thì có thể sẽ có vài đỉnh có 3 cạnh nối với nó không phải cha con của nhau. Nếu cạnh nối từ ~u~ đến ~par~ giống với một cạnh khác thì ta sẽ đi xuống đỉnh có cạnh khác với hai cạnh còn lại. Nếu ta đi đến đỉnh còn lại thì sẽ có trường hợp mà điều kiện sẽ không thỏa. Ta sẽ dfs như vậy đến khi gặp đỉnh lá thì sẽ cho nó làm gốc rồi tính đáp án của bài toán.

- Độ phức tạp ~O(N \log_2 N)~

Subtask 4

- Để xác định một đỉnh có là gốc được hay không, ta sẽ xem có hai cạnh nào (ở cùng độ cao) cùng được gán một kí tự hay không. Để tối ưu, ta sẽ tính ~dp_u~ là số cặp cạnh có độ cao bằng nhau, có cùng kí tự trong cây con gốc ~u~ .Sau đó ta dùng dp reroot.

- Độ phức tạp ~O(N)~

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define print_op(...) ostream& operator<<(ostream& out, const __VA_ARGS__& u)
#define db(val) "["#val" = "<<(val)<<"] "
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL
#   define clog cerr << setw(__db_level * 2) << setfill(' ') << "" << setw(0)
#   define DB() debug_block CONCAT(dbbl, __LINE__)
    int __db_level = 0;
    struct debug_block {
        debug_block() { clog << "{" << endl; ++__db_level; }
        ~debug_block() { --__db_level; clog << "}" << endl; }
    };
#else
#   define clog if (0) cerr
#   define DB(...)
#endif
template<class U, class V> print_op(pair<U, V>) {
    return out << "(" << u.first << ", " << u.second << ")";
}
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& con) {
    out << "{";
    for (auto beg = con.begin(), it = beg; it != con.end(); ++it)
        out << (it == beg ? "" : ", ") << *it;
    return out << "}";
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")";
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup);
}
template<class ...U> print_op(tuple<U...>) {
    return print_tuple_utils<0, tuple<U...>>(out, u);
}
template <typename A, typename B> bool maximize(A& a, B b) {
    return a < b ? a = b, true : false;
}
template <typename A, typename B> bool minimize(A& a, B b) {
    return a > b ? a = b, true : false;
}

const int N = 1e5 + 5;

int n;
vector<pair<int, char>> adj[N];
ll d[N];
int res = 0;

void dfs(int u, int par) {
    vector<int> cnt(26);
    for (auto v : adj[u]) {
        if (v.first == par) continue;
        ++ cnt[v.second - 'a'];
        dfs(v.first, u);
        d[u] += d[v.first];
    }
    for (int i = 0; i < 26; ++ i) {
        d[u] += 1LL * cnt[i] * (cnt[i] - 1) / 2;
    }
}

void dfs2(int u, int par, int preChar) {
    vector<int> cnt(26);
    for (auto v : adj[u]) {
        if (v.first == par) continue;
        ++ cnt[v.second - 'a'];
    }
    if (par) {
        d[u] -= 1ll * cnt[preChar - 'a'] * (cnt[preChar - 'a'] - 1) / 2;
        ++ cnt[preChar - 'a'];
        d[u] += 1ll * cnt[preChar - 'a'] * (cnt[preChar - 'a'] - 1) / 2;
    }
    if (d[u] == 0) {
        ++ res;
    }
    clog << db(u) << db(cnt) << db(d[u]) << endl;
    for (auto [v, c] : adj[u]) {
        if (v == par) continue;
        ll tmp = d[u] - d[v] - 1ll * cnt[c - 'a'] * (cnt[c - 'a'] - 1) / 2;
        tmp += 1ll * (cnt[c - 'a'] - 1) * (cnt[c - 'a'] - 2) / 2;
        d[v] += tmp;
        clog << db(v) << db(tmp) << endl;
        dfs2(v, u, c);
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        adj[i].clear();
        d[i] = 0;
    }
    res = 0;
    for (int i = 1; i < n; ++ i) {
        int u, v;
        char c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
    dfs(1, 0);
    dfs2(1, 0, 0);
    cout << res << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
#endif
    int tt=1;
   // cin >> tt;
    while (tt --)
    solve();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}