21 Days Training // Day 7

2. tree

My idea : still enumrate.
Code :

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    int N;cin >> N;
    int W[N];
    for (int i=0;i<N;i++) cin >> W[i];
    string S[N];
    for (int i=0;i<N;i++) cin >> S[i];
    map<int, set<int> > G, subs;
    for (int i=0;i<N-1;i++) {
        int u, v;cin >> u >> v;u--;v--;
        if (G.find(u)==G.end()) G[u]=set<int>();
        if (G.find(v)==G.end()) G[v]=set<int>();
        G[u].insert(v);
        G[v].insert(u);
    }
    set<int> vis;
    queue<int> Q, Qas;
    Q.push(0);
    while (!Q.empty()) {
        int cur=Q.front();Q.pop();
        vis.insert(cur);
        subs[cur] = set<int>();
        for (set<int>::iterator it=G[cur].begin();it!=G[cur].end();it++) {
            int nxt=(*it);
            if (vis.find(nxt)!=vis.end()) continue;
            subs[cur].insert(nxt);
            Q.push(nxt);
        }
    }
    long long ans[N];
    memset(ans, 0, sizeof(ans));
    for (int i=0;i<N;i++) {
        vector<int> Ns;
        Qas.push(i);
        while (!Qas.empty()) {
            int cur=Qas.front();Qas.pop();
            Ns.push_back(cur);
            for (set<int>::iterator it=subs[cur].begin();it!=subs[cur].end();it++) Qas.push((*it));
        }
        sort(Ns.begin(), Ns.end());
        for (int j=0;j<Ns.size()-1;j++) {
            for (int k=j+1;k<Ns.size();k++) {
                int l;
                for (l=0;l<min(S[Ns[j]].length(), S[Ns[k]].length());l++) {
                    if (S[Ns[j]][l]!=S[Ns[k]][l]) break;
                }
                ans[i] += (W[Ns[j]]^W[Ns[k]])*l;
            }
        }
    }
    for (int i=0;i<N;i++) cout << ans[i] << endl;
    return 0;
}

Complexity : about O(n^3)
Constraints :

Expected : 15/15