#P18659. LaLa and Harvesting

    ID: 17995 传统题 4000ms 1024MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-最大权独立集顶点覆盖全子集枚举仙人掌图low-linkDFS 序树形 DP路径恢复

LaLa and Harvesting

LaLa and Harvesting

每隔一个冬天,拉拉都会帮助她的姨妈爱夏收获一种碧海利尔王国特有的作物。

这种作物可以用一张图表示:边对应枝条,顶点对应枝条的连接处,每个连接处u都长着一个美味程度为T_u的果实。

作物的培育分为三个阶段。

  1. 第一阶段开始时,在空地上种下一颗种子。种子最终长成一张仙人掌图:它是一张简单连通图,其中每条边至多属于一个环。这是唯一会长出新连接处的阶段。
  2. 考虑第一阶段仙人掌图的一棵DFS树。第二阶段开始时,爱夏用环形支架围住作物,并把DFS树的叶子连接到支架上。这里的叶子指仅计DFS树的边时无向度数为1的顶点,因此可能包括DFS树的根。这样会使作物在支架上相邻的连接处之间长出额外枝条,形成一张环图,并开始结果。具体构造见输入说明。
  3. 第三阶段开始时,爱夏把一个魔法工具接到支架上,为作物不断补充额外养分,于是又长出一些枝条。本阶段长出的枝条的并集形成一棵非常“茂密”的树:其中每个非叶顶点的度数都至少为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

样例说明

下图表示样例描述的作物。

样例三阶段枝条,原PDF插图

  • 黑色实线表示第一阶段长出并属于DFS树的枝条;
  • 黑色虚线表示第一阶段长出但不属于DFS树的枝条;
  • 红色边表示第二阶段长出的枝条;
  • 蓝色边表示第三阶段长出的枝条。

注意,同一对连接处之间可能有多条直接连接的枝条。