Untitled

mail@pastecode.io avatar
unknown
c_cpp
22 days ago
3.5 kB
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std ; 
#ifndef ONLINE_JUDGE
#include "debugger.cpp"
#else
#define debug(...)
#define debugArr(...)
#define show(...)
#endif
template<typename... T>void read(T&... args) {((cin >> args), ...);}
template<typename... T>void print(T&&... args) {((cout << args ), ...);}
template <class T> using V = vector<T>;
#define pb push_back
typedef long long ll ; typedef array<int, 2> pi ; typedef vector<int> vi ; 
#define len(v) (int)v.size()
#define FOR( i , debut,  fin) for( ll i = debut ; i<fin ; i++   )
#define all(x) x.begin(), x.end() 
#define getunique(vt)  vt.erase(unique(all(vt)), vt.end()) 
void YES(bool x) { if (x) cout << ("Yes\n"); else cout << ("No\n"); }
const int MAX_MASK = (1 << 26) + 1;

void input_output();
const int N = 3e5 + 10; 
int n ; 
vector<pi>adj[N]; 
vi nodes ; 
int depth[N] , parent[N] , pfxor[N] , in[N] , out[N] ,big[N] ;   
int freq[MAX_MASK]  ;  
int timer = -1 ; 
void calsz ( int nd , int pr , int xpf   ){
    depth[nd] = 1 ;
    pfxor[nd] = xpf ; 
    in[nd] = ++timer ; 
    nodes.push_back(nd);
    int mx = -1 , u = -1 ; 
    for ( auto &[ch,_]:  adj[nd]){
        if ( ch == pr ) continue;
        calsz(ch , nd  , xpf ^ _   );
        parent[ch] = nd ;   
        depth[nd] += depth[ch];
        if (mx < depth[ch]) {
            u = ch ;
            mx = depth[ch];
        } 
    }
    out[nd] = timer ; 
    big[nd] = u;
}
ll ans = 0 ;
void smalltobig(int node, int p, int keep = 1) {
    for ( auto &[ch,w]:adj[node]){
        if ( ch == p or ch == big[node] )continue; 
        else smalltobig(ch,node,0);
    }
    if ( big[node] != -1 )  smalltobig(big[node],node,1);
    int prfparent =pfxor[node] ;
    int needed1 = prfparent ;
    
    ans += freq[needed1]  ; 
    for ( int bt = 0 ; bt < 26 ; bt++ ){
        int x = 1LL << bt ; 
        int need2 = prfparent ^ x ; 
        ans += freq[need2] ;
    }
    freq[prfparent]++ ;  
    for ( auto &[ch,_] :adj[node]){
        if ( ch == p or ch == big[node] ) continue;
        for ( int i = in[ch]; i <= out[ch] ; i++ ){
            int nodehere = nodes[i];
            ans += freq[pfxor[nodehere]];
            for ( int j = 0 ; j < 26 ; j++ ){
                int x = 1LL << j ; 
                int need2 = pfxor[nodehere] ^ x ; 
                ans += freq[need2];
            }
        }
        for ( int i = in[ch] ; i <= out[ch] ;i++ ){
            int nodehere = nodes[i];
            freq[pfxor[nodehere]]++ ; 
        }
    }
    if ( keep == 0 ) {
        for (int i=in[node];i<=out[node];++i) {
            int nodehere=nodes[i];
            freq[pfxor[nodehere]]--;
        }
    }
}
 
void solve(){
    read (n);
    ans = 0 ;
    timer = -1 ; 
    FOR (i , 0 , n-1 ){
        int u , v ; 
        char a ; 
        read ( u , v , a  );
        int msk = 1LL << (a- 'a') ;
        adj[u].push_back({v,msk});
        adj[v].push_back({u,msk});
    }
    pfxor[0] = 0 ;
    calsz(1 , 0 , 0 );
    smalltobig(1,0);
    print(ans); 
}
    

int32_t main() {
    input_output();
    int t = 1;
    for ( int i = 1 ; i <= t ; i++ ){
        show("------- Case " , i, "------- : " );
        solve();
        show("---------------------- .\n \n ");      
    }     
    double Time_elapsed= 1.0 * clock() / CLOCKS_PER_SEC ; 
    debug(Time_elapsed);
        
}


void input_output() {
    cout.tie(0), cin.tie(0), ios_base::sync_with_stdio(0) ; 
    #ifndef ONLINE_JUDGE 
    freopen("inp.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("err.txt", "w", stderr); 
    #endif
}
Leave a Comment