# Overview:

ACdream 群【第三次原創群賽】將於【11月17日星期六晚19點】進行。本次原創群賽由[sjtu]ftiasch（人稱 GXX 神牛、叉妹）出題。歡迎大家積极參与～【冠軍】和【ACdreamOJ第10000次提交】的ID我們將會贈送小禮品一份 。。 比賽傳送門。。。。

（。。。看樣子叉娘不願意在 blog 里貼太學術的東西。。。以下授權轉發。。。
ac-dream-3rd.tar （題目、標程、解題報告、測試數據。。。

# Official Solutions:

## Product

$v(A) = \frac{\prod_{a \in A}(1 + a) – \prod_{a \in A}(1 – a)}{2}$

## Path

#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100000;

int n, q, parent[N];

int find(int i) {
return parent[i] == -1 ? i : (parent[i] = find(parent[i]));
}

int edge_count, first_edge[N], to[N << 1], length[N << 1], next_edge[N << 1];

const int INF = 100000000;

int down[N][2], limit[2];

void add_edge(int u, int v, int w) {
to[edge_count] = v;
length[edge_count] = w;
next_edge[edge_count] = first_edge[u];
first_edge[u] = edge_count ++;
}

#define UPDATE(x, a) x = max(x, a)

void dfs(int p, int u) {
down[u][0] = 0;
down[u][1] = -INF;
for (int iter = first_edge[u]; iter != -1; iter = next_edge[iter]) {
int v = to[iter];
int l = length[iter];
if (v != p) {
dfs(u, v);
for (int x = 0; x < 2; ++ x) {
for (int y = 0; y < 2; ++ y) {
UPDATE(limit[x + y + l & 1], down[u][x] + down[v][y] + l);
}
}
for (int y = 0; y < 2; ++ y) {
UPDATE(down[u][y + l & 1], down[v][y] + l);
}
}
}
}

int main() {
assert(scanf("%d%d", &n, &q) == 2);
assert(1 <= n && n <= N);
assert(1 <= q && q <= N);
memset(parent, -1, sizeof(parent));
edge_count = 0;
memset(first_edge, -1, sizeof(first_edge));
for (int i = 0; i < n - 1; ++ i) {
int a, b, c;
assert(scanf("%d%d%d", &a, &b, &c) == 3);
assert(1 <= a && a <= n);
assert(1 <= b && b <= n);
assert(1 <= c && c <= 2);
a --;
b --;
assert(find(a) != find(b));
parent[find(a)] = find(b);
}
limit[0] = limit[1] = -INF;
dfs(-1, 0);
while (q --) {
int l;
assert(scanf("%d", &l) == 1);
if (l < 0) {
puts("No");
} else {
int t = l % 2;
puts(l <= limit[t] ? "Yes" : "No");
}
}
return 0;
}



## Multiplication

$C[k] = (A[1] + A[2] + \cdots + A[k]) \cdot B[k] + (B[1] + B[2] + \cdots + B[k]) \cdot A[k] – A[k] \cdot B[k]$

## Matching

#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100;
const int MOD = 1000000000 + 7;

int n, a[N][N];

int inverse(int a) {
return a == 1 ? 1 : (long long)(MOD - MOD / a) * inverse(MOD % a) % MOD;
}

int main() {
assert(scanf("%d", &n) == 1);
assert(1 <= n && n <= N);
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < n; ++ j) {
assert(scanf("%d", &a[i][j]) == 1);
}
}
for (int i = 0; i < n; ++ i) {
assert(a[i][i] == 0);
for (int j = 0; j < n; ++ j) {
assert(a[i][j] == a[j][i]);
assert(a[i][j] == 0 || a[i][j] == 1);
}
}
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < n; ++ j) {
if (a[i][j]) {
a[i][j] = rand() % MOD;
a[j][i] = MOD - a[i][j];
}
}
}
int rank = 0;
for (int i = 0; i < n; ++ i) {
int pivot = rank;
while (pivot < n && !a[pivot][i]) {
pivot ++;
}
if (pivot < n) {
for (int j = 0; j < n; ++ j) {
swap(a[rank][j], a[pivot][j]);
}
{
int times = inverse(a[rank][i]);
for (int j = 0; j < n; ++ j) {
a[rank][j] = (long long)a[rank][j] * times % MOD;
}
for (int k = 0; k < n; ++ k) {
if (k != rank && a[k][i]) {
int times = a[k][i];
for (int j = 0; j < n; ++ j) {
(a[k][j] += MOD - (long long)a[rank][j] * times % MOD) %= MOD;
}
}
}
}
rank ++;
}
}
assert(!(rank & 1));
printf("%d\n", rank >> 1);
return 0;
}

/* .................................................................................................................................. */

const int N = 369;

int P[N], F[N], B[N], Q[N], head, tail;
bool G[N][N], InB[N], inQ[N]; int mark[N], tot;
int n, s, t, match;

#define pre F[P[i]]
int lca(int u, int v){
++tot; RST(mark);
for (int i=u;i;i=pre){ i=B[i]; mark[i]=tot; }
for (int i=v;i;i=pre){ i=B[i]; if (mark[i]==tot) return i;}
}

void blossoming(int u,int v){

int z = lca(u, v); RST(InB);

for (int i=u;B[i]!=z;i=pre){
if (B[pre]!=z) F[pre]=P[i];
InB[B[i]]=true;
InB[B[P[i]]]=true;
}
for (int i=v;B[i]!=z;i=pre){
if (B[pre]!=z) F[pre]=P[i]; //同理
InB[B[i]]=true;
InB[B[P[i]]]=true;
}

if (B[u]!=z) F[u]=v;
if (B[v]!=z) F[v]=u;
REP_1(i, n)
if (InB[B[i]]){
B[i]=z;
if (!inQ[i]){
Q[tail++]=i;
inQ[i]=true;
}
}
}

void change(){
int x,y,z=t; while (z){
y=F[z], x=P[y];
P[y]=z, P[z]=y, z=x;
}
}

bool bfs(){

RST(F, inQ); REP_1(i, n) B[i] = i;

REP_1(v, n) if (G[u][v] && B[u]!=B[v] && P[u]!=v){
if (s==v || P[v] && F[P[v]]) blossoming(u,v);
else if (!F[v]){
F[v] = u; if (P[v]){
Q[tail++] = P[v];
inQ[P[v]] = true;
}
else{
t = v, change();
return true;
}
}
}
}
return false;

}

int EBC(){
int match = 0; RST(P); REP_1_N(s, n) if (!P[s] && bfs()) ++match;
return match;
}

void init(){
RD(n); REP_2_1(i, j, n, n) RD(G[i][j]);
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif

init(); OT(EBC());
}



## Component

"熟知的動態規劃演算法"可以參見何森的集訓隊論文。

#include <cassert>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 2000;
const int INF = 1000000000;

int n, weight[N], parent[N], answer[N + 1];

int find(int i) {
return parent[i] == -1 ? i : find(parent[i]);
}

bool mark[N];
int size[N], max_tree[N];
vector <int> nodes;
int minimum[N + 1][N + 1];

#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)

void dfs(int p, int u) {
size[u] = 1;
max_tree[u] = 0;
nodes.push_back(u);
int v = *iter;
if (v != p && !mark[v]) {
dfs(u, v);
size[u] += size[v];
max_tree[u] = max(max_tree[u], size[v]);
}
}
}

void divide(int root) {
nodes.clear();
dfs(-1, root);
int total = size[root];
int new_root = -1;
int min_cost = INF;
foreach (iter, nodes) {
int u = *iter;
int ret = max(total - size[u], max_tree[u]);
if (ret < min_cost) {
new_root = u;
min_cost = ret;
}
}
nodes.clear();
dfs(-1, new_root);
int m = nodes.size();
minimum[m][0] = 0;
for (int i = 1; i <= m; ++ i) {
minimum[m][i] = INF;
}
for (int i = m - 1; i >= 0; -- i) {
int id = nodes[i];
for (int j = 0; j <= m; ++ j) {
minimum[i][j] = minimum[i + size[id]][j];
if (j) {
minimum[i][j] = min(minimum[i][j], minimum[i + 1][j - 1] + weight[id]);
}
}
}
for (int j = 1; j <= m; ++ j) {
}
mark[new_root] = true;
int v = *iter;
if (!mark[v]) {
divide(v);
}
}
}

int main() {
assert(scanf("%d", &n) == 1);
assert(1 <= n && n <= N);
for (int i = 0; i < n; ++ i) {
assert(scanf("%d", weight + i) == 1);
assert(1 <= weight[i] && weight[i] <= 1000000);
}
memset(parent, -1, sizeof(parent));
for (int i = 0; i < n - 1; ++ i) {
int a, b;
assert(scanf("%d%d", &a, &b) == 2);
a --;
b --;
assert(find(a) != find(b));
parent[find(a)] = find(b);
}
for (int i = 1; i <= n; ++ i) {
}
memset(mark, 0, sizeof(mark));
divide(0);
for (int i = 1; i <= n; ++ i) {
printf("%d%c", answer[i], i == n ? '\n' : ' ' );
}
return 0;
}

/* .................................................................................................................................. */

const int N = 3009;

int A[N], f[N], dp[N][N];
VI adj[N]; bool vis[N]; int sz[N];
int n, res;

void dfs(int u){
vis[u] = true, sz[u] = 1;
FLC(dp[u], 0x3f), dp[u][1] = A[u];

dfs(v), sz[u] += sz[v];
DWN_1(j, sz[u], 2) DWN_1(k, min(sz[v], j-1), 1) // 剪枝 .. .
checkMin(dp[u][j], dp[u][j-k] + dp[v][k]);
}
REP_1(i, sz[u]) checkMin(f[i], dp[u][i]);
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif

REP_1_C(i, RD(n)) RD(A[i]);

FLC(f, 0x3f); DO(n-1){
int x, y; RD(x, y);