#P18659. LaLa and Harvesting
LaLa and Harvesting
LaLa and Harvesting
每隔一个冬天,拉拉都会帮助她的姨妈爱夏收获一种碧海利尔王国特有的作物。
这种作物可以用一张图表示:边对应枝条,顶点对应枝条的连接处,每个连接处u都长着一个美味程度为T_u的果实。
作物的培育分为三个阶段。
- 第一阶段开始时,在空地上种下一颗种子。种子最终长成一张仙人掌图:它是一张简单连通图,其中每条边至多属于一个环。这是唯一会长出新连接处的阶段。
- 考虑第一阶段仙人掌图的一棵DFS树。第二阶段开始时,爱夏用环形支架围住作物,并把DFS树的叶子连接到支架上。这里的叶子指仅计DFS树的边时无向度数为1的顶点,因此可能包括DFS树的根。这样会使作物在支架上相邻的连接处之间长出额外枝条,形成一张环图,并开始结果。具体构造见输入说明。
- 第三阶段开始时,爱夏把一个魔法工具接到支架上,为作物不断补充额外养分,于是又长出一些枝条。本阶段长出的枝条的并集形成一棵非常“茂密”的树:其中每个非叶顶点的度数都至少为12。第三阶段结束时开始收获。
拉拉希望收获的果实美味程度之和最大。不过,她不能同时收获两个相邻连接处的果实,否则会伤害并杀死直接连接它们的所有枝条。
请计算一个拉拉可以收获的果实集合,使其美味程度之和最大。
输入格式
输入只有一组,格式如下:
N M
T_0 T_1 ... T_(N-1)
u_0 v_0
u_1 v_1
...
u_(M-1) v_(M-1)
K
x_0 y_0
x_1 y_1
...
x_(K-1) y_(K-1)
N是连接处的数量,编号为0到N−1。M是第一阶段长出的枝条数,第i条连接u_i和v_i。
在第一阶段的仙人掌图上,从顶点0开始DFS。**每个顶点的邻边都按它们在输入中出现的先后顺序访问,越早输入的边越优先。**这唯一确定了DFS的先序访问顺序及对应的DFS树。取这个DFS访问顺序中所有在DFS树中无向度数为1的顶点,得到子序列c_0,...,c_(l−1)。第二阶段增加的l条边依次是:
(c_0,c_1), (c_1,c_2), ..., (c_(l-2),c_(l-1)), (c_(l-1),c_0)
K是第三阶段长出的枝条数,第i条连接x_i和y_i。
所有输入满足:
- 所有数都是整数;
- 2≤N≤500,N−1≤M≤2N,1≤K≤min(N−1,100);
- 对所有0≤u<N,有1≤T_u≤200000;
- 对所有0≤i<M,有0≤u_i<v_i<N;第一阶段没有重复的无向边;
- 对所有0≤i<K,有0≤x_i<y_i<N;第三阶段没有重复的无向边;
- 第一阶段的边在顶点集{0,1,...,N−1}上构成仙人掌图;
- 第三阶段的边在其端点集{x_0,y_0,x_1,y_1,...,x_(K−1),y_(K−1)}上构成一棵树,其中每个度数大于1的顶点的度数都至少为12。这棵树不必包含全部N个顶点。
不同生长阶段的边可以重合。若l=2,第二阶段的两条环边连接同一对顶点,这也是原题允许的情形。
输出格式
输出格式为:
W L
s_0 s_1 ... s_(L-1)
W是可以收获的美味程度最大总和,s={s_0,...,s_(L−1)}是达到该值的果实集合。输出必须满足:
- 所有数都是整数;
- 0≤L≤N;
- 0≤s_0<s_1<...<s_(L−1)<N,即编号必须严格递增;
- 对任意0≤i<j<L,三个阶段长出的所有枝条中,没有直接连接s_i和s_j的边;
- T_(s_0)+...+T_(s_(L−1))=W。
如果有多个最优集合,输出任意一个。空白分隔方式不影响判定。
样例输入 1
6 7
1 1 1 1 1 1
0 1
1 2
2 3
2 4
1 5
1 4
0 5
1
2 5
样例输出 1
2 2
0 4
样例说明
下图表示样例描述的作物。

- 黑色实线表示第一阶段长出并属于DFS树的枝条;
- 黑色虚线表示第一阶段长出但不属于DFS树的枝条;
- 红色边表示第二阶段长出的枝条;
- 蓝色边表示第三阶段长出的枝条。
注意,同一对连接处之间可能有多条直接连接的枝条。