题意：给定树和长为m的序列。对于每个长为偶数的子串，你都要在树上将这些点以最小代价两两匹配。求总代价。
解：考虑贪心匹配。如果一个子树内有奇数个备选点，那么这个边的贡献 + 1。
考虑每条边的贡献，只需知道每条边的子树这些点，有多少个长为偶数的区间把它们包含了奇数次。
发现可以维护奇偶位置前缀和的奇偶性个数。然后乘一下。注意这里的前缀和，开头是以l为下标1，而不是以l为下标l，且空节点的前缀和全部为0，要注意。
然后用线段树合并维护这些前缀和即可，对每条边统计答案。
1 #include <bits/stdc++.h> 2 3 typedef long long LL; 4 5 const int N = 600010, MO = 998244353; 6 7 struct Edge { 8 int nex, v, len; 9 }edge[N << 1]; int tp; 10 11 int n, e[N], a[N], ans, rt[N], m; 12 13 namespace seg { 14 const int V = 15000000; 15 int ls[V], rs[V], sum[2][2][V], siz[V], sl[2][2], sr[2][2], tot; 16 inline void pushup(int l, int r, int o) { 17 int mid = (l + r) >> 1, L = ls[o], R = rs[o], len = mid - l + 1, len2 = r - mid; 18 int f = (mid - l + 1) & 1, f2 = siz[L] & 1; 19 20 siz[o] = siz[L] + siz[R]; 21 22 if(L) { 23 sl[0][0] = sum[0][0][L]; 24 sl[0][1] = sum[0][1][L]; 25 sl[1][0] = sum[1][0][L]; 26 sl[1][1] = sum[1][1][L]; 27 } 28 else { 29 sl[0][0] = len >> 1; 30 sl[0][1] = 0; 31 sl[1][0] = (len + 1) >> 1; 32 sl[1][1] = 0; 33 } 34 35 if(R) { 36 sr[0][0] = sum[0][0][R]; 37 sr[0][1] = sum[0][1][R]; 38 sr[1][0] = sum[1][0][R]; 39 sr[1][1] = sum[1][1][R]; 40 } 41 else { 42 sr[0][0] = len2 >> 1; 43 sr[0][1] = 0; 44 sr[1][0] = (len2 + 1) >> 1; 45 sr[1][1] = 0; 46 } 47 48 sum[0][0][o] = sl[0][0] + sr[f][f2]; 49 sum[0][1][o] = sl[0][1] + sr[f][f2 ^ 1]; 50 sum[1][0][o] = sl[1][0] + sr[f ^ 1][f2]; 51 sum[1][1][o] = sl[1][1] + sr[f ^ 1][f2 ^ 1]; 52 return; 53 } 54 void insert(int p, int l, int r, int &o) { 55 if(!o) { 56 o = ++tot; 57 } 58 if(l == r) { 59 siz[o] = sum[1][1][o] = 1; 60 return; 61 } 62 int mid = (l + r) >> 1; 63 if(p <= mid) { 64 insert(p, l, mid, ls[o]); 65 } 66 else { 67 insert(p, mid + 1, r, rs[o]); 68 } 69 pushup(l, r, o); 70 return; 71 } 72 int merge(int x, int y, int l, int r) { 73 if(!x || !y) { 74 return x | y; 75 } 76 int mid = (l + r) >> 1; 77 ls[x] = merge(ls[x], ls[y], l, mid); 78 rs[x] = merge(rs[x], rs[y], mid + 1, r); 79 pushup(l, r, x); 80 return x; 81 } 82 83 inline void calc(int x, int v) { 84 int temp = (LL)(sum[0][0][x] + 1) * sum[0][1][x] % MO; 85 //printf("temp = %d \n", temp); 86 temp = (temp + (LL)sum[1][0][x] * sum[1][1][x] % MO) % MO; 87 //printf("temp += %d * %d\n", sum[1][0][x], sum[1][1][x]); 88 ans = (ans + (LL)temp * v % MO) % MO; 89 //printf("ans += %d * %d \n", temp, v); 90 return; 91 } 92 } 93 94 inline void add(int x, int y, int z) { 95 edge[++tp].v = y; 96 edge[tp].len = z; 97 edge[tp].nex = e[x]; 98 e[x] = tp; 99 return; 100 } 101 102 void DFS(int x, int fa, int v) { 103 for(int i = e[x]; i; i = edge[i].nex) { 104 int y = edge[i].v; 105 if(y == fa) { 106 continue; 107 } 108 DFS(y, x, edge[i].len); 109 rt[x] = seg::merge(rt[x], rt[y], 1, m); 110 } 111 //printf("x = %d \n", x); 112 seg::calc(rt[x], v); 113 return; 114 } 115 116 int main() { 117 118 freopen("electricity.in", "r", stdin); 119 freopen("electricity.out", "w", stdout); 120 121 scanf("%d%d", &n, &m); 122 int x, y; 123 LL z; 124 for(int i = 1; i < n; i++) { 125 scanf("%d%d%lld", &x, &y, &z); 126 add(x, y, z); 127 add(y, x, z); 128 } 129 for(int i = 1; i <= m; i++) { 130 scanf("%d", &a[i]); 131 seg::insert(i, 1, m, rt[a[i]]); 132 } 133 134 DFS(1, 0, 0); 135 136 printf("%d\n", ans); 137 return 0; 138 } 139 /* 140 4 4 141 1 2 1 142 2 3 2 143 3 4 1 144 2 3 1 4 145 ------------------------ 146 11 147 */
原文：https://www.cnblogs.com/huyufeifei/p/11101001.html
