题目描述

小明参加了一个夺宝游戏，游戏的规则是这样的，有一个树形迷宫，树上的每个节点ti都包含价值为ai的宝物，树上的每条边都有一个标记li。

在树上，只能从父亲节点向儿子节点开始走，1号节点为树的根节点。

在游戏开始时，小明的初始位置会被指定为树的某个节点，小明需要给出一个长度为k的标记序列（k不小于0），从开始节点沿着这个序列进行运动，直到对应的位置，拿到该位置对应的宝物。

但是，小明发现了这个游戏存在一些漏洞，因为每条边的标记可能相同。

因此，指定的标记序列可能有多个终点，而主办方会把每个符合条件的终点的宝物均取出来作为小明的奖品。

现在小明想知道在哪个点出发，获得宝物的价值最高，因此他有Q个问题，需要聪明的你帮他解答一下。

输入格式
第一行包含两个整数N和Q。

第二行包含N个整数ai，表示每个节点的宝物的价值。

接下来N-1行，每行包含两个整数u，v和一个小写字母q，表示u和v之间存在一个标记为q的边。

接下来Q行，每行包含一个整数ti，表示询问从ti点出发，能获取的最大的宝物的价值是多少。

输出格式
输出共Q行，每行包含一个询问中，能获取的最大宝物的价值。

数据范围
1≤N,Q≤20000,
0≤ai≤1000,
1≤u,v≤N,
′a′≤q≤‘z′
树的结构是随机生成的。

样例

输入
5 5
1 2 3 4 5
1 2 a
1 3 a
3 4 b
3 5 b
1
2
3
4
5
输出
9
2
9
4
5

算法1

(dfs) $O(nlogn)$

树的结构是随机生成的。高度的期望不会超过logn
所以直接暴力dfs
时间复杂度为o( nlog( n ) )

注意邻接表的两种方式

一种是数组模拟

int h[ N ], e[ M ], ne[ M ], idx;
memset( h, - 1, sizeof( h ) );
idx = 0;


void add( int a, int b )
{
    e[ idx ] = b; ne[ idx ] = h[ a ]; h[ a ] = idx ++;
}

for( int i = h[ x ]; ~i; i = ne[ i ] ) cout << e[ i ] << endl;

执行add( x, 2 );
执行add( x, 3 );
执行add( x, 4 );
执行add( x, 5 );
遍历点的跟输入是反向的，即 5 -> 4 -> 3 -> 2

一种是vector< int > 存储

vector< int > h[ N ];

h[ x ].push_back( 2 );
h[ x ].push_back( 3 );
h[ x ].push_back( 4 );
h[ x ].push_back( 5 );
遍历点的跟输入是同向的，即 2 -> 3 -> 4 -> 5

C++ 代码

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

typedef unsigned long long ULL;

const int N = 200010, M = N * 2, P = 131;

int val[ N ], ans[ N ];
int h[ N ], e[ M ], ne[ M ], ch[ M ], idx;
int n, q;

void add( int a, int b, int c )
{
    e[ idx ] = b;
    ch[ idx ] = c;
    ne[ idx ] = h[ a ];
    h[ a ] = idx ++;
}

unordered_map< ULL, int > dfs( int u,int father )
{
    unordered_map< ULL, int > heap;
    heap[ 0 ] = val[ u ];
    ans[ u ] = 0;
    for( int i = h[ u ]; ~i; i = ne[ i ] )
    {
        if( e[ i ] == father ) continue;
        auto S = dfs( e[ i ], u );
        for( auto x: S ) heap[ x.first * P + ch[ i ] ] += x.second;
    }
    for( auto x: heap ) ans[ u ] = max( ans[ u ], x.second );
    return heap;
}

int main()
{
    scanf( "%d %d", &n, &q );
    memset( h, -1, sizeof( h ) );
    idx = 0;
    for( int i = 1; i <= n; i ++ ) scanf( "%d", &val[ i ] );
    for( int i = 1; i < n; i ++ )
    {
        int a, b;
        char c[ 2 ];
        scanf( "%d%d%s", &a, &b, c );
        add( a, b, *c );
        add( b, a, *c );
    }
    dfs( 1, - 1 );

    for( int i = 1; i <= q; i ++ )
    {
        int x;
        scanf( "%d", &x );
        printf( "%d\n", ans[ x ] );
    }
    return 0;
}