下载 #2 数据自测是预处理深度和父子关系的时候堆栈溢出(深度2e4+......)。看第一篇题解也是递归深搜能过，那么就是我的代码出问题了...

完整代码5.89kb就不放在这里了

评测记录&完整代码见此

相关代码片段:

struct Node
{
    ll val;
    int fa, fst, siz, dep, hson, num;
    // fst-遍历起点边,hson-重儿子,num-链中位置
} nd[MAXN | 1];

struct Edge
{
    int nxt, to;
} ed[MAXN << 1 | 1];

inline void add_edge(int u, int v)
{
    ed[++numEd].nxt = nd[u].fst;
    nd[u].fst = numEd;
    ed[numEd].to = v;
    return;
}

void pre_dfs(int x, int fa)
{
    int tmp = 0;
    nd[x].siz = 1;
    for (int i = nd[x].fst; i; i = ed[i].nxt)
        if (ed[i].to != fa)
        {
            register int y = ed[i].to;
            nd[y].fa = x;
            nd[y].dep = nd[x].dep + 1;
            pre_dfs(y, x);
            nd[x].siz += nd[y].siz;
            if (nd[y].siz > tmp)
            {
                tmp = nd[y].siz;
                nd[x].hson = y;
            }
        }
    return;
}

inline void INIT()
{
    n = qread();
    m = qread();
    s = qread();
    mod = qread();
    for (int i = 1; i <= n; ++i)
        nd[i].val = qread();
    for (int i = 1; i < n; ++i)
    {
        u = qread();
        v = qread();
        add_edge(u, v);
        add_edge(v, u);
    }
    return;
} // 读入

inline void PRE()
{
    pre_dfs(s, 0);
    // 处理树
    build_chain(s, s);
    // 剖分
    build_segtree(1, 0, n);
    // 建线段树
    return;
} // 预处理