题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<unordered_map>

using namespace std;

typedef unsigned long long ULL;
const int N = 20010, M = 2 * N, P = 131;
int h[N], e[M], ne[M], ch[M], idx;
int v[N];
int ans[N];
int n, m;
unordered_map<ULL, int> dfs(int u, int father)
{
    unordered_map<ULL, int> hash;
    hash[0] = v[u];
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != father)
        {
            for (auto x : dfs(j, u)) 
                hash[x.first * P + ch[i]] += x.second;
        }
    }
    for (auto x : hash) ans[u] = max(ans[u], x.second);
    return hash;

}
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], ch[idx] = c, h[a] = idx ++;
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> v[i];
    for (int i = 1; i < n; i ++)
    {
        int a, b;
        string c;
        cin >> a >> b >> c;
        add(a, b, c[0]);
        add(b, a, c[0]);
    }
    dfs(1, -1);
    for (int i = 0; i < m; i ++)
    {
        int x;
        cin >> x;
        cout << ans[x] << endl;
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla