配对树。
题面已经足够清楚。
Subtask 1
不难想到枚举序列里面所有长度为偶数的区间，然后剩下就还剩一个 \(O(n)\) 供我们来计算匹配整个区间的代价。
不妨设 \(dp_{i,j}\) 为在 \(i\) 的子树中剩下 \(j\) 个点没有匹配的代价，然后看一下每条边需要被覆盖几次来计算答案。
但是这样显然不是一个很聪明的做法。因为我们不可能把一对子树内的点拉出去斩了匹配，所以如果要最小代价的话一定有 \(j \in [0,1]\)。
所以可以 \(O(n)\) 树形 dp。总复杂度 \(O(m^2n)\)。
Subtask 2
显然 Subtask 1 的方法比较有前途，考虑继续观察性质。
注意到对于一个 ddl 区间，一条边在最终匹配方案中被覆盖，当且仅当删去这条边之后出来的两个块中，包含的 ddl 的数量都为奇数。
所以一条 \(u \to v\) 的边（\(u\) 为父亲，\(v\) 为儿子）被覆盖当且仅当 \(v\) 的子树中的 ddl 数目为奇数。
考虑改造 Subtask 1 的做法，反过来，计算一条边会被多少个 ddl 区间覆盖。
对于一条树边，将其子树内的 ddl 都标为 \(1\)，其余的标为 \(0\)，则问题转换为了求解 \(01\) 串中包含奇数个 \(1\) 的偶区间个数。设这个 \(01\) 串为 \(s\)。很显然可以直接使用前缀和维护对 \(2\) 的余数的方法来计算这个值。复杂度是 \(O(m)\) 的。
而得到 \(01\) 串是 \(O(n)\) 的。因为有 \(n-1\) 条树边，所以总复杂度 \(O(n(n+m))\)。
upd：为了 Subtask 4 的讲解，我来先铺垫一下怎么使用前缀和计算。
设 \(sum_{i,k\in\{0,1\},j\in\{0/1\}}\) 为 \(0\le l \le i,l \equiv k (\text{mod} \ 2),s_l = j\) 的个数。
每一次直接维护，继承上一个结果，然后更新。最终答案显然是 \(sum_{n,0,0}\times sum_{n,0,1} + sum_{n,1,0} \times sum_{n,1,1}\)。
Subtask 3
又发现 Subtask 3 的 \(m\) 又与 Subtask 1 一样了，考虑同样改造 Subtask 1 的做法。
假设我们已经有一个确定的 ddl 偶区间，发现如果一个点不和任意一个区间里面的点有关系，则这个点本身是无意义的。
所以考虑一下有意义的点有多少，显然只会是区间里面的点两两之间的 lca。所以直接建虚树，然后按照 Subtask 1 的方法暴力即可。
复杂度为 \(O(m^3 \log m)\)。
Subtask 4
又发现这里的 \(n\) 和 Subtask 2 的一模一样，所以考虑延续 Subtask 2 的做法。
怎么这么多延续。
题外话：由此，可以看出部分分的设计不无道理，往往部分分之间会有关联，这种关联会启发最终的正解。
不妨使用某种数据结构来维护子树形成的 \(01\) 串。
可以发现，我们只需要在这个数据结构上面维护区间的四个 \(sum\) 值，然后对于一个区间，通过左半段里面的 \(1\) 的数量来决定右半段是否要反转（因为左边的 \(1\) 会影响右边的前缀和的 \(1\) 的数量的奇偶性），就可以 \(O(1)\) 来维护区间 \(sum\)。最终的需要的答案会落在根结点上。显然可以使用线段树来维护。
然后枚举每一条树边，加入里面的所有子树，就可以 \(O(n^2 \log m)\) 计算。
其实可以发现到现在就已经 \(50\) 分了。
Subtask 5
看起来很神秘，但实际上没啥用处，只是保证了点很均衡。到时候讲正解就直接把它包含了。
Subtask 6
发现这个时候树是随机的，其他地方没有特殊点。这启发我们人类智慧。
我们充分发扬人类智慧，我们依旧枚举每一条树边，并加入里面的所有子树。虽然这样看似是 \(O(n^2)\) 的，但是对于每一个点，其只会被加入期望 \(O(\log n)\) 次。
于是总共也就只是加入 \(O(n \log n \log m)\) 次，在 \(n,m \le 10^5\) 的时候都可以在 1s 内卡过。
Subtask 7
其实看到 Subtask 6 的最终复杂度里面有一个 \(\log n \log m\)，这个时候就启发我们最终的复杂度大概也会带一个 \(\log n\log m\)。
因为 Subtask 5 和 Subtask 6 都比较 trivial，和本身题目的解法没有啥关系。所以考虑延续 Subtask 4 的解法。
注意到原来的解法中每一次都是把 ddl 清空之后再重新加入。因为子树之间具有包含的关系，所以这样很重复计算，很浪费时间。
考虑对于一个结点 \(u\)，我们在遍历完它的最后一个儿子之后，不清空它的修改，而是将 \(u\) 的其他儿子的 ddl 都加到这个修改里面。显然这样是可行的，而且节约了一定时间。设 \(u\) 到其最后一个儿子的边叫做“重边”。
但是这样复杂度还是有点险，考虑继续思考。注意到，一个点被加入的次数，就是其到根结点的路径上“非重边”的个数。
这个时候正解就已经比较显然了，因为这样很像 dsu on tree。所以，如果最后一个儿子是 \(u\) 的重儿子，复杂度就可以做到 \(O(n \log n \log m)\) 。\(\log m\) 是在线段树上面修改得来的。
所以，考虑求出重儿子，然后再求出来所有儿子的结果之后，将轻儿子的结果加到重儿子里面，最终加的次数就是 \(O(n \log n)\)，然后就是最终 \(O(n \log n \log m)\)，可以通过。
Bonus
注意到现在不太可以通过了，Extra Test 实在有些毒瘤。
再次从 Subtask 4 开始想。注意到可以直接线段树合并乱搞，而我们知道 \(m\) 个结点合并之后地时间复杂度是 \(O(m \log m)\)。
所以最终时间复杂度 \(O(n+m \log m)\)，虽然空间复杂度是 \(m \log m\)，不过也无伤大雅。
#include <bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
using namespace std;
const int N = 100010, mod = 998244353;
int n, m;
vector<pair<int, int> > v[N];
int rt[N];
int id;
int ls[N * 40], rs[N * 40];struct node {int c0, c1;int siz;
} seg[N * 40];void pushup(int x, int l, int r) {seg[x].siz = seg[ls[x]].siz + seg[rs[x]].siz;int l1, l2;l1 = r / 2 - mid / 2, l2 = r - mid - l1;if (seg[ls[x]].siz % 2) {seg[x].c0 = seg[ls[x]].c0 + l1 - seg[rs[x]].c0;seg[x].c1 = seg[ls[x]].c1 + l2 - seg[rs[x]].c1;} else {seg[x].c0 = seg[ls[x]].c0 + seg[rs[x]].c0;seg[x].c1 = seg[ls[x]].c1 + seg[rs[x]].c1;}
}void insert(int &x, int l, int r, int p) {if (!x)x = ++id;if (l == r) {seg[x].siz = 1;if (p % 2 == 0)seg[x].c0 = 1;elseseg[x].c1 = 1;return ;}if (p <= mid)insert(ls[x], l, mid, p);elseinsert(rs[x], mid + 1, r, p);pushup(x, l, r);
}int merge(int x, int y, int l, int r) {if (!x || !y)return x + y;ls[x] = merge(ls[x], ls[y], l, mid);rs[x] = merge(rs[x], rs[y], mid + 1, r);pushup(x, l, r);return x;
}
int as = 0;void dfs(int u, int pre, int inv) {for (auto [i, w] : v[u]) {if (i == pre)continue;dfs(i, u, w);rt[u] = merge(rt[u], rt[i], 1, m);}if (u == 1)return ;int ans = 0;ans = (ans + seg[rt[u]].c0*(m / 2 + 1 - seg[rt[u]].c0) % mod) % mod;ans = (ans + seg[rt[u]].c1*((m + 1) / 2 - seg[rt[u]].c1) % mod) % mod;as = (as + ans *inv % mod) % mod;
}signed main() {cin >> n >> m;for (int i = 1; i < n; i++) {int x, y, z;cin >> x >> y >> z;v[x].push_back({y, z});v[y].push_back({x, z});}for (int i = 1; i <= m; i++) {int x;cin >> x;insert(rt[x], 1, m, i);}dfs(1, 0, 0);cout << as << endl;return 0;
}总结
感觉这道题的分数配置很妙，如果按照子任务一个一个地想就可以按部就班的想到正解。
如果把其中的一些 Subtask 删掉，这道题的难度就会直线上升，因为这道题地算法就是线段树 + dsu on tree，比较难想。