NOI 2018 网络同步赛。

（听说 dzd 讲话很赛艇，听说社会活动很…？）

开幕式讲课全程 B 站直播好评！

时隔若干个星期后的再一次爆零记（这两天根本没有状态。。。）

CTSC/APIO 2018 接着爆零记。
（爆零三连。。。）

ZJOI Day2 继续爆零记。（依然无需划去）

题意：

给定一张 $n$ 个顶点 $m$ 条边的无向图 ( 顶点编号为 $1,2,\ldots,n$)，每条边上带有权值。所有权值都可以分解成 $2^a \times 3^b$ 的形式。

现在有 $q$ 个询问，每次询问给定四个参数 $u$、$v$、$a$ 和 $b$，请你求出是否存在一条顶点 $u$ 到 $v$ 之间的路径（不一定为简单路径），使得路径依次经过的边上的权值的最小公倍数为 $2 ^ a \times 3 ^ b$

$1 \le n,q \le 50000、1 \le m \le 100000、0 \le a,b \le 10^9$

最近 Codeforces 的比赛打的有点少。( 其实有几场 Div2 在口胡算法。。。)

来回顾一下做过的为数不多的几道题目。（只讲重点思路，看完整解法请右转 “Tutorial” 板块，锻炼英语能力）

首先提供官方题解：

2016 之前
较新的题解

UPD: 民间题解：集训队作业

另外，TopCoder 的插件中，moj 做得不错，repo （最新版浮点数 spj 在 c++11 下不会 CE 了， Emacs 选手可能需要手动调整缩进，当然有 java 编译器的可以自己动手改～）

最近在 CF 上出现了一道斯特林数 (Stirling Number) 的题（CF960G， HDU 上 有解法相同的一道题）,（在 ZJOI Day1 讲课的时候也提到了）。

所以先来总结一波公式。

题意：

给定序列 A，序列中的每一项 $A_i$ 有删除代价 $B_i$ 和附加属性 $C_i$。请删除若干项，使得 A 的最长上升子序列长度减少至少 1，且付出的代价之和最小，并输出方案。如果有多种方案，请输出将删去项的附加属性排序之后，字典序最小的一种。

$n \leq 700$

题意：

给出一棵树，有 $m$ 次操作，每次操作为标记一条路径并给它一个权值，或删除一个标记。每次操作后找出一条路径，使得其经过的标记过的路径的权值和最大 ( 一条路径经过另一条路径当且仅当这两条路径有公共点 )， 输出最大的权值和。 $n, m \le 10 ^ 5$.