[UOJ 195][ZJOI2016]大♂森林
ETT野蛮，LCT文明，，，
换生长结点这个操作非常的麻烦。所以考虑给每个生长操作建立一个虚点，每个实点（就是在树中真实存在的点）向他之前最晚建立的一个虚点认父。
然后虚点初始的时候应该向上一次的那个虚点认父（我们可以近似的认为第一个虚点就是1）。然后我们用类似于扫描线的做法，等到了虚点存在的区间里就把它爸爸改成相应的实点，出去了相应区间之后就再改回来。这样这题就很好做了，我们认为虚点点权为0，实点点权为1，然后查询就好做了。
然后还有一点细节问题……比如说换生长结点的时候如何处理x在某一棵树里不存在的情况。但这个不难处理，因为同一个编号的结点一定分布编号连续的一段树里，所以真实起作用的操作范围可以认定为数据给出的操作范围和x的分布区间的交。
再有一点就是查询的时候……如果直接查询两点间splay的和的话，可能会忽略掉一些本来在原图上该有的实点。所以我们要求两点到根的距离，再用LCA去掉不需要的。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <vector>
#include <utility>
const int maxn = 100005;
const int maxm = 200005;
const int maxs = maxm + maxm;
struct Node {
Node *fa, *ch[2];
int val, sumv;
bool rev;
int d() {
return ((this == fa -> ch[1]) ? 1 : 0);
}
void sc(Node *c, int dir) {
ch[dir] = c;
c -> fa = this;
}
void maintain() {
sumv = ch[0] -> sumv + ch[1] -> sumv + val;
}
void paint() {
rev = !rev;
std::swap(ch[0], ch[1]);
}
void pushdown() {
if(rev) {
ch[0] -> paint();
ch[1] -> paint();
rev = false;
}
}
};
Node pool[maxs];
Node *nil, *cur;
void init_pool() {
nil = cur = pool;
nil -> val = nil -> sumv = 0;
nil -> rev = false;
nil -> fa = nil -> ch[0] = nil -> ch[1] = nil;
}
#define T(x) (pool + (x))
Node *refresh(Node *x, int val = 0) {
x -> val = x -> sumv = val;
x -> rev = false;
x -> fa = x -> ch[0] = x -> ch[1] = nil;
return x;
}
bool is_root(Node *x) {
return (x -> fa == nil || (x -> fa -> ch[0] != x && x -> fa -> ch[1] != x));
}
void zig(Node *x) {
Node *y = x -> fa; int d = x -> d();
if(is_root(y)) {
x -> fa = y -> fa;
} else {
y -> fa -> sc(x, y -> d());
}
y -> sc(x -> ch[1 ^ d], d);
x -> sc(y, 1 ^ d);
y -> maintain(); x -> maintain();
}
void splay(Node *x) {
while(!is_root(x)) {
Node *y = x -> fa;
if(!is_root(y)) y -> fa -> pushdown();
y -> pushdown(); x -> pushdown();
if(!is_root(y)) {
if((x -> d()) ^ (y -> d())) {
zig(x);
} else {
zig(y);
}
}
zig(x);
}
// x -> maintain();
}
Node *access(Node *x) {
Node *nx = x, *y = nil;
Node *ct = T(1);
while(x != nil) {
splay(x); x -> pushdown();
if(x -> fa == nil) ct = x;
x -> sc(y, 1); x -> maintain();
y = x; x = x -> fa;
}
splay(nx); return ct;
}
Node *evert(Node *x) {
access(x); x -> paint();
return x;
}
void link(Node *x, Node *y) {
evert(x); x -> fa = y;
}
void cut(Node *x) {
access(x);
x -> ch[0] -> fa = nil;
x -> ch[0] = nil; x -> maintain();
}
void cut(Node *x, Node *y) {
evert(x); access(y);
int d = x -> d();
y -> ch[d] = nil; y -> maintain();
x -> fa = nil;
}
int ans[maxm];
using pii = std::pair<int, int>;
int n;
pii seg_and(int a, int b, int x, int y) {
if(a > x) {
std::swap(a, x), std::swap(b, y);
}
if(b < x) return std::make_pair(n + 1, n + 1);
if(b >= y) return std::make_pair(x, y);
return std::make_pair(x, b);
}
int ope[maxm][4];
int seg[maxm][2];
Node *bef[maxm];
std::vector<int> beg[maxn], end[maxn];
std::vector<int> query[maxn];
// #define OUTP
// #define LOCAL
int main() {
#ifdef OUTP
freopen("forest1.in", "r", stdin);
freopen("out", "w+", stdout);
#endif
int m; scanf("%d%d", &n, &m);
init_pool(); refresh(T(1), 1);
int cnt0 = 1, cnt1 = 0, cnt2 = 0;
Node *last1 = T(1);
seg[1][0] = 1; seg[1][1] = n;
for(int i = 1; i <= m; i ++) {
scanf("%d%d%d", &ope[i][0], &ope[i][1], &ope[i][2]);
if(ope[i][0]) {
scanf("%d", &ope[i][3]);
}
if(ope[i][0] == 0) {
int c = ++ cnt0;
refresh(T(c), 1);
link(last1, T(c));
seg[c][0] = ope[i][1]; seg[c][1] = ope[i][2];
#ifdef LOCAL
printf("Node %d : (%d, %d)\n", c, seg[c][0], seg[c][1]);
#endif
} else if(ope[i][0] == 1) {
Node *n1 = T(m + i);
refresh(n1); link(n1, bef[i] = last1);
int l = ope[i][1], r = ope[i][2], x = ope[i][3];
auto s = seg_and(l, r, seg[x][0], seg[x][1]);
l = s.first, r = s.second;
#ifdef LOCAL
printf("Change : (%d, %d) -> %d\n", l, r, x);
#endif
beg[l].push_back(i); end[r + 1].push_back(i);
last1 = n1;
} else {
int x = ope[i][1], u = ope[i][2], v = ope[i][3];
query[x].push_back(i);
}
}
for(int i = 1; i <= n; i ++) {
for(auto id : end[i]) {
Node *n1 = T(m + id);
cut(n1, T(ope[id][3])); link(n1, bef[id]);
}
for(auto id : beg[i]) {
Node *n1 = T(m + id);
cut(n1, bef[id]); link(n1, T(ope[id][3]));
}
for(auto id : query[i]) {
int u = ope[id][2], v = ope[id][3];
evert(T(1)); access(T(u));
int ret = T(u) -> sumv;
Node *lca = access(T(v));
ret += T(v) -> sumv;
access(lca);
ret -= lca -> sumv;
ret -= lca -> sumv - 1;
ans[id] = ret - 1;
}
}
for(int i = 1; i <= m; i ++) {
if(ope[i][0] == 2) {
printf("%d\n", ans[i]);
}
}
return 0;
}
[LibreOJ 2137][ZJOI2015]诸神眷顾的幻想乡
复习SAM了呢~
那个度数为1的点至多有20个的条件非常神奇……让我们想想怎么用。
我们发现，（钦定根后）在树上有一条路径是弯的这种情况非常不好统计，但如果是直着下来就很好说（把所有从根到一个点的路径扔到SAM里，然后是经典题）。但是，任何一条路一定会在某个度数为1的点为根的情况下是直的（可以意会一下吧（逃
然后我们从那20个点每个点当根DFS一遍，把搞出来的每一条从根开始的路径放前缀Trie里。然后对前缀Trie构一个SAM就行啦~
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
const int BUFSIZE = 128 * 1024 * 1024;
char buf[BUFSIZE];
void *alloc(size_t size) {
static char *cur = buf;
if(cur - buf + size > BUFSIZE) {
return malloc(size);
} else {
char *ret = cur; cur += size;
return ret;
}
}
const int maxn = 100005;
std::vector<int> G[maxn];
int deg[maxn];
int ssiz;
struct TNode {
TNode *ch[10];
};
TNode *alloc_tn() {
auto ret = (TNode*)alloc(sizeof(TNode));
memset(ret -> ch, 0, sizeof(ret -> ch));
return ret;
}
TNode *step(TNode *o, int c) {
if(!(o -> ch[c])) {
o -> ch[c] = alloc_tn();
}
return (o -> ch[c]);
}
TNode *trt;
int col[maxn];
void dfs(int x, int fa, TNode *last) {
TNode *np = step(last, col[x]);
for(auto v : G[x]) {
if(v != fa) {
dfs(v, x, np);
}
}
}
struct Node {
int len; Node *fa;
Node *ch[10];
};
std::vector<Node*> pool;
Node *alloc_node(int len = 0, Node *fa = NULL) {
Node *ret = (Node*)alloc(sizeof(Node));
ret -> len = len; ret -> fa = fa;
memset(ret -> ch, 0, sizeof(ret -> ch));
pool.push_back(ret);
return ret;
}
Node *rt;
Node *extend(int c, Node *last) {
Node *np = alloc_node(last -> len + 1);
Node *p = last;
while(p != NULL && p -> ch[c] == NULL) {
p -> ch[c] = np; p = p -> fa;
}
if(p == NULL) {
np -> fa = rt;
} else {
Node *q = p -> ch[c];
if(q -> len == p -> len + 1) {
np -> fa = q;
} else {
Node *nq = alloc_node(p -> len + 1, q -> fa);
memcpy(nq -> ch, q -> ch, sizeof(q -> ch));
q -> fa = np -> fa = nq;
while(p != NULL && p -> ch[c] == q) {
p -> ch[c] = nq; p = p -> fa;
}
}
}
return np;
}
void dfs_2(TNode *o, Node *last) {
for(int i = 0; i < ssiz; i ++) {
TNode *v = o -> ch[i];
if(!v) continue;
Node *np = extend(i, last);
dfs_2(v, np);
}
}
using ll = long long;
int main() {
int n; scanf("%d%d", &n, &ssiz);
for(int i = 1; i <= n; i ++) {
scanf("%d", &col[i]);
}
trt = alloc_tn();
for(int i = 1; i <= n - 1; i ++) {
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v); G[v].push_back(u);
deg[u] ++; deg[v] ++;
}
for(int i = 1; i <= n; i ++) {
if(deg[i] == 1) {
dfs(i, 0, trt);
}
}
rt = alloc_node();
dfs_2(trt, rt);
ll ans = 0;
for(auto p : pool) {
if(p -> fa) {
ans += p -> len - p -> fa -> len;
}
}
printf("%lld\n", ans);
return 0;
}
[BZOJ 3527][ZJOI2014]力
现在才明白卷积真的是the deep, dark fantasies……（逃
首先约去\(q_i\)，得到：
\[E_j = \sum_{i < j}\frac{q_i}{(j - i)^2} - \sum_{j < i}\frac{q_i}{(j - i)^2}\]
注意到如果很容易得到等式前半部分的高效求法，后半部分把序列反过来就能做了。
那么我们会发现，设\(g_x = \frac{1}{x^2}\)，然后式子前半部分（姑且称作\(p_j\)）可表示为：
\[p_j = \sum_{i < j} q_i g_{j - i}\]
这不就是个卷积吗？FFT一波即可。
代码：
/**************************************************************
Problem: 3527
User: danihao123
Language: C++
Result: Accepted
Time:9984 ms
Memory:28952 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <cassert>
#include <complex>
typedef long double R;
typedef std::complex<R> C;
const R eps = 1e-3;
int sign(R x) {
if(fabs(x) < eps) {
return 0;
} else {
if(x < 0) {
return -1;
} else {
return 1;
}
}
}
const int maxn = 400005;
const double pi = acos(-1);
int bi, len;
int flip(int x) {
int ans = 0;
for(int i = 0; i < bi; i ++) {
if(x & (1 << i)) {
ans += 1 << (bi - i - 1);
}
}
return ans;
}
void fft(C *A, double g = 1) {
for(int i = 0; i < len; i ++) {
int R = flip(i);
#ifdef LOCAL
// printf("The flipping of %d is %d\n", i, R);
#endif
if(i < R) {
std::swap(A[R], A[i]);
}
}
for(int L = 1; L < len; L <<= 1) {
C xi_n(cos(pi / (double(L))), sin(g * pi / (double(L))));
for(int i = 0; i < len; i += L << 1) {
C xi(1, 0);
for(int j = i; j < i + L; j ++) {
C a = A[j], b = A[j + L];
A[j] = a + xi * b;
A[j + L] = a - xi * b;
xi = xi * xi_n;
}
}
}
}
int main() {
int n;
static C A[maxn], rd[maxn]; static R ans[maxn];
static R q[maxn];
scanf("%d", &n);
bi = 0; len = 1;
while(len <= 2 * n) {
len <<= 1;
bi ++;
}
for(int i = 0; i < n; i ++) {
scanf("%Lf", &q[i]); A[i] = q[i];
}
assert(sign(rd[0].real()) == 0);
for(int i = 1; i < n; i ++) {
rd[i] = 1.00 / ((R(i)) * (R(i)));
#ifdef LOCAL
printf("rd[%d] : %.5Lf\n", i, rd[i].real());
#endif
}
fft(A); fft(rd);
for(int i = 0; i < len; i ++) A[i] *= rd[i];
fft(A, -1);
for(int i = 0; i < n; i ++) {
ans[i] += A[i].real() / len;
#ifdef LOCAL
printf("delta_v of %d : %.5Lf\n", i, A[i].real() / len);
#endif
}
std::reverse(q, q + n);
for(int i = 0; i < len; i ++) A[i] = 0;
for(int i = 0; i < n; i ++) {
A[i] = q[i];
}
fft(A);
for(int i = 0; i < len; i ++) A[i] *= rd[i];
fft(A, -1);
for(int i = 0; i < n; i ++) {
ans[i] -= A[n - 1 - i].real() / len;
printf("%.3Lf\n", ans[i]);
}
return 0;
}
[LibreOJ 2135][ZJOI2015]幻想乡战略游戏
竟然1A了蛤蛤蛤蛤蛤
这题用人话说就是给你一个不会动的树，让你求带权重心。
先解决一个问题：如果要求动态修改点权，并且要求多次询问求某点\(x\)的\(\sum_{i = 1}^n d_i\cdot dist(i, x)\)，怎么做？
很显然对于一个点\(x\)，对它造成贡献的点，可能是在以\(x\)为根的点分子树里的，也可能在\(x\)之外。但是一个不在该点分子树内的点要对\(x\)产生贡献，必须要经过\(x\)在分治树上的祖先。
所以我们可以考虑对每个重心，记录下它这个点分子树中所有点对该重心的贡献、对点分树上的父亲的贡献以及该点分子树的点权和。每次求答案时\(x\)所在的分治子树的贡献很好考虑，那考虑一下其分治树上祖先对\(x\)的贡献就行了。
那带权重心怎么求呢？如果我们把树的根变成带权重心，那么我们会发现越远离根则答案越劣。所以我们如果只往使得答案更小的地方走，那么最后一定会走到带权重心上。
我们考虑把这个过程放点分树上。从整棵树的重心开始往下走，每次如果发现有一条出边指向的点答案更好，那就往这个子结构（不是指向的点而是那个联通块的重心，否则时间复杂度不对）里走。最后走不动了，走到的点就是带权重心了。
求LCA我用的是\(O(logn)\)的树剖而不是\(O(1)\)搞法，但是跑的贼快（可能和树剖常数小有关？）。
吐槽一点，原题提到了每个点的度数不超过20，但是网上几乎所有OJ上该题的题面都没提到这一点……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <set>
#include <vector>
#include <queue>
#include <stack>
typedef long long ll;
const int maxn = 100005;
const int maxe = maxn << 1;
int first[maxn];
int next[maxe], to[maxe];
ll dist[maxe];
void add_edge(int u, int v, ll d) {
static int cnt = 0;
cnt ++;
next[cnt] = first[u];
first[u] = cnt;
to[cnt] = v;
dist[cnt] = d;
}
int n;
int size[maxn], hson[maxn], fa[maxn], dep[maxn];
ll dis[maxn];
void dfs_1(int x, int father = 0, int depth = 1, ll d = 0) {
size[x] = 1;
fa[x] = father;
dep[x] = depth;
dis[x] = d;
int max_siz = 0;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(v != father) {
dfs_1(v, x, depth + 1, d + dist[i]);
size[x] += size[v];
if(size[v] > max_siz) {
max_siz = size[v];
hson[x] = v;
}
}
}
}
int dfn[maxn], top[maxn], tid[maxn];
void dfs_2(int x, int father = 0, int a = 1) {
static int dfn_clk = 0;
dfn[x] = ++ dfn_clk;
tid[dfn[x]] = x;
top[x] = a;
if(!hson[x]) {
return;
} else {
dfs_2(hson[x], x, a);
}
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(v != father && v != hson[x]) {
dfs_2(v, x, v);
}
}
}
int lca(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
x = fa[top[x]];
}
if(dep[x] > dep[y]) {
return y;
} else {
return x;
}
}
ll calc_dist(int x, int y) {
int l = lca(x, y);
return dis[x] + dis[y] - 2LL * dis[l];
}
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int f = 0) {
siz[x] = 1;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && v != f) {
gen_siz(v, x);
siz[x] += siz[v];
}
}
}
int nrt, rt;
void gen_rt(int x, int f = 0) {
bool flag = (siz[x] * 2 >= siz[nrt]);
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && v != f) {
flag = (flag && (siz[v] * 2 <= siz[nrt]));
gen_rt(v, x);
}
}
if(flag) rt = x;
}
ll w[maxn];
int crt, cfa[maxn];
ll pans[maxn], give[maxn], sumv[maxn];
int point2[maxe];
/*
void search_p(int x, std::stack<int> *V, int f = 0) {
V -> push(x);
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && v != f) {
search_p(v, V, x);
}
}
}
*/
int divide(int x) {
nrt = rt = x;
gen_siz(x); gen_rt(x);
x = rt; vis[x] = true;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v]) {
int ch = divide(v);
point2[i] = ch;
cfa[ch] = x;
}
}
return x;
}
void update(int x, ll delta) {
int p = x;
while(p) {
pans[p] += delta * calc_dist(p, x);
if(p != crt) give[p] += delta * calc_dist(x, cfa[p]);
sumv[p] += delta;
p = cfa[p];
}
}
ll get_ans(int x) {
ll ans = pans[x];
int p = x;
while(p != crt) {
int f = cfa[p];
ans += pans[f] - give[p];
ans += calc_dist(x, f) * (sumv[f] - sumv[p]);
p = cfa[p];
}
return ans;
}
ll get_best() {
int p = crt;
std::stack<int> S;
ll now_ans;
while(true) {
S.push(p); vis[p] = true;
bool fix = true;
now_ans = get_ans(p);
for(int i = first[p]; i; i = next[i]) {
int v = to[i];
if(vis[v]) continue;
if(get_ans(v) < now_ans) {
fix = false;
p = point2[i];
break;
}
}
if(fix) break;
}
while(!S.empty()) {
int u = S.top(); S.pop();
vis[u] = false;
}
return now_ans;
}
int main() {
int q; scanf("%d%d", &n, &q);
for(int i = 0; i < n - 1; i ++) {
int u, v; ll d; scanf("%d%d%lld", &u, &v, &d);
add_edge(u, v, d); add_edge(v, u, d);
}
dfs_1(1); dfs_2(1);
crt = divide(1); memset(vis, 0, sizeof(vis));
while(q --) {
int u, e; scanf("%d%d", &u, &e);
update(u, e);
printf("%lld\n", get_best());
}
return 0;
}
[BZOJ 3925][ZJOI2015]地震后的幻想乡
赛艇，赛艇.jpg
首先这个问题的本质就是让你求一个边权在\([0, 1]\)间均匀随机分布的无向图的MST的最大边边权的期望……
有一个很经典的式子：
\[E = \int_0^1 p(\geq x)\,\mathrm{d}x\]
然后考虑那个\(p\)咋整。
首先对于每个包含1的点集（我们不妨假设是从点1开始扩展）\(S\)，式子可以这么写（这里不妨用\(T\)来表示两个点集间的边的数目）：
\[p_{S, x} = \sum_{1\in S_0 \subset S} (1 - x)^{T(S_0, S - S_0)}(1 - p_{S_0, x})\]
显然答案是\(\int_0^1 p_{S, x}\,\mathrm{d}x\)，但这玩咋求……
然后我们定义一个状态\(d\)：
\[d_{S, k} = \int_0^1 (1 - x)^k p_{S, x}\,\mathrm{d}x\]
把其中的\(p\)展开，整理一下，得到：
\[
\begin{aligned}
d_{S, k}=&\sum_{1\in S_0 \subset S}(\int_0^1(1 - x)^{T(S, S - S_0) + k}\,\mathrm{d}x\\
& - \int_0^1(1 - x)^{T(S, S - S_0) + k}\,p_{S_0,\,x}\,\mathrm{d}x)
\end{aligned}
\]
\begin{aligned}
d_{S, k}=&\sum_{1\in S_0 \subset S}(\int_0^1(1 - x)^{T(S, S - S_0) + k}\,\mathrm{d}x\\
& - \int_0^1(1 - x)^{T(S, S - S_0) + k}\,p_{S_0,\,x}\,\mathrm{d}x)
\end{aligned}
\]
里面有两大块定积分，前一块还看起来蛮好求的，但后面一块……
不就是\(d_{S_0, T(S, S - S_0) + k}\) 吗？
然后这样整个$d$就可以搞一波状压DP了。
然后观察\(d_{S, 0}\)（这里不妨假设S为全集）：
\[d_{S, 0}=\int_0^1(1 - x)^0 p_{S, x}\,\mathrm{d}x = \int_0^1 p_{S, x}\,\mathrm{d}x\]
这不就是我们要的答案吗？
至于边界处理，\(d_{\{1\}, x}\)全部搞成0就行。
代码：
/**************************************************************
Problem: 3925
User: danihao123
Language: C++
Result: Accepted
Time:100 ms
Memory:1272 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <bitset>
typedef double R;
const int maxn = 11;
const int maxm = 50;
int edge[maxm][2];
int n, m;
R d[1 << 10][maxm];
bool vis[1 << 10][maxm];
R f(int s, int k) {
if(s == 1) return 0;
if(vis[s][k]) return d[s][k];
d[s][k] = 0;
int lit_s = s >> 1;
for(int lit_s0 = (lit_s - 1) & lit_s; ; lit_s0 = (lit_s0 - 1) & lit_s) {
int s0 = lit_s0 * 2 + 1;
int t = 0;
for(int i = 1; i <= m; i ++) {
int u = edge[i][0], v = edge[i][1];
if(((1 << u) & s) == 0 || ((1 << v) & s) == 0) continue;
if((((1 << u) & s0) == 0) ^ (((1 << v) & s0) == 0)) {
t ++;
}
}
int z = k + t;
d[s][k] += 1.00 / ((double(z)) + 1.00) - f(s0, z);
if(s0 == 1) break;
}
vis[s][k] = true;
return d[s][k];
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++) {
int u, v; scanf("%d%d", &u, &v); u --, v --;
edge[i][0] = u, edge[i][1] = v;
}
printf("%.6lf\n", f((1 << n) - 1, 0));
return 0;
}
[BZOJ 1095][ZJOI2007]Hide 捉迷藏
蛤蛤蛤我这题终于调出来了~（然后1A了）
点分树处女作。其实点分树的思想并不难理解，就是把点分的过程抽象化到一棵树上。
其实唯一比较烦人的就是点分树上的儿子给父亲的贡献要开一个堆处理……非常烦人。
代码（其中有海量本来拿来调试的代码，慎读）：
/**************************************************************
Problem: 1095
User: danihao123
Language: C++
Result: Accepted
Time:15268 ms
Memory:128944 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <set>
#include <vector>
#include <queue>
const int maxn = 100005;
const int maxe = maxn << 1;
int first[maxn];
int next[maxe], to[maxe];
void add_edge(int u, int v) {
static int cnt = 0;
cnt ++;
next[cnt] = first[u];
first[u] = cnt;
to[cnt] = v;
}
int size[maxn], hson[maxn], fa[maxn], dep[maxn];
void dfs_1(int x, int father = 0, int depth = 1) {
size[x] = 1;
fa[x] = father;
dep[x] = depth;
int max_siz = 0;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(v != father) {
dfs_1(v, x, depth + 1);
size[x] += size[v];
if(size[v] > max_siz) {
max_siz = size[v];
hson[x] = v;
}
}
}
}
int dfn[maxn], top[maxn], tid[maxn];
void dfs_2(int x, int father = 0, int a = 1) {
static int dfn_clk = 0;
dfn[x] = ++ dfn_clk;
tid[dfn[x]] = x;
top[x] = a;
if(!hson[x]) {
return;
} else {
dfs_2(hson[x], x, a);
}
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(v != father && v != hson[x]) {
dfs_2(v, x, v);
}
}
}
int lca(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
x = fa[top[x]];
}
if(dep[x] > dep[y]) {
return y;
} else {
return x;
}
}
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int fa = 0) {
siz[x] = 1;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && v != fa) {
gen_siz(v, x);
siz[x] += siz[v];
}
}
}
int nrt, rt;
void gen_rt(int x, int fa = 0) {
bool ok = (2 * siz[x] >= siz[nrt]);
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && v != fa) {
ok = ok && (2 * siz[v] <= siz[nrt]);
gen_rt(v, x);
}
}
if(ok) rt = x;
}
int crt;
int cfa[maxn];
typedef std::priority_queue<int> heap;
struct dheap {
heap Q, D;
void push(int x) {
Q.push(x);
}
void pop() {
while(!D.empty() && Q.top() == D.top()) {
#ifdef DEBUG
printf("deleting %d\n", D.top());
#endif
Q.pop(); D.pop();
}
Q.pop();
}
int top() {
while(!D.empty() && Q.top() == D.top()) {
#ifdef DEBUG
printf("deleting %d\n", D.top());
#endif
Q.pop(); D.pop();
}
return Q.top();
}
void del(int x) {
D.push(x);
}
size_t size() {
return Q.size() - D.size();
}
int sec() {
int fir = top(); pop();
int ret = top(); push(fir);
return ret;
}
};
dheap all;
dheap Q[maxn], sg[maxn];
int divide(int x) {
nrt = rt = x;
gen_siz(x); gen_rt(x);
x = rt; vis[x] = true;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v]) {
cfa[divide(v)] = x;
}
}
return x;
}
int n;
int get_ans(dheap &q) {
return q.top() + q.sec();
}
bool sta[maxn];
int dist(int x, int y) {
int ret = dep[x] + dep[y] - 2 * dep[lca(x, y)];
#ifdef DEBUG
printf("dist(%d, %d) : %d\n", x, y, ret);
#endif
return ret;
}
void light_on(int p) {
sta[p] = true;
int x = p;
int og = -1, ng = 0;
while(x) {
int old_ans = -1, old_sg = -1;
if(Q[x].size() > 1) {
old_ans = get_ans(Q[x]);
}
if(sg[x].size() > 0) {
old_sg = sg[x].top();
}
if(og != -1) Q[x].del(og);
if(ng != -1) Q[x].push(ng);
if(Q[x].size() > 1) all.push(get_ans(Q[x]));
if(old_ans != -1) all.del(old_ans);
if(cfa[x] != 0) {
og = old_sg;
sg[x].push(dist(p, cfa[x]));
ng = sg[x].top();
}
x = cfa[x];
}
}
void light_off(int p) {
sta[p] = false;
int x = p;
int og = 0, ng = -1;
while(x) {
int old_ans = -1, old_sg = -1;
if(Q[x].size() > 1) old_ans = get_ans(Q[x]);
if(sg[x].size() > 0) {
old_sg = sg[x].top();
}
if(og != -1) Q[x].del(og);
if(ng != -1) Q[x].push(ng);
#ifdef DEBUG
printf("%d deleting %d\n", x, og);
#endif
if(Q[x].size() > 1) all.push(get_ans(Q[x]));
if(old_ans != -1) all.del(old_ans);
#ifdef DEBUG
int tmp = -1;
if(Q[x].size() > 1) tmp = get_ans(Q[x]);
printf("ans of %d : %d -> %d\n", x, old_ans, tmp);
#endif
if(cfa[x] != 0) {
og = old_sg;
sg[x].del(dist(p, cfa[x]));
if(sg[x].size() > 0) {
ng = sg[x].top();
} else {
ng = -1;
}
}
x = cfa[x];
}
}
void print_dheap(dheap &q) {
std::vector<int> V;
while(q.size() > 0) {
int t = q.top(); q.pop();
printf("%d ", t);
V.push_back(t);
}
puts("");
for(int i = 0; i < V.size(); i ++) {
q.push(V[i]);
}
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n - 1; i ++) {
int u, v; scanf("%d%d", &u, &v);
add_edge(u, v); add_edge(v, u);
}
dfs_1(1); dfs_2(1);
#ifdef DEBUG
for(int i = 1; i <= n; i ++) {
printf("%d top fa hson : %d %d %d\n", i, top[i], fa[i], hson[i]);
}
#endif
crt = divide(1);
#ifdef DEBUG
printf("crt id %d\n", crt);
for(int i = 1; i <= n; i ++) {
printf("cfa[%d] : %d\n", i, cfa[i]);
}
#endif
int num = 0;
for(int i = 1; i <= n; i ++) {
light_on(i); num ++;
#ifdef DEBUG
printf("heap while inserting %d : ", i);
print_dheap(all);
#endif
}
int q; scanf("%d", &q);
while(q --) {
char op[3]; scanf("%s", op);
if(op[0] == 'G') {
if(num == 0) {
puts("-1");
} else if(num == 1) {
puts("0");
} else {
printf("%d\n", all.top());
}
} else {
int i; scanf("%d", &i);
if(sta[i]) {
light_off(i);
num --;
} else {
light_on(i);
num ++;
}
}
#ifdef DEBUG
print_dheap(all);
#endif
}
return 0;
}
[BZOJ 1034]泡泡堂
这题其实就是一个田忌赛马类问题。贪心即可。
如果你不知道田忌赛马怎么贪，可以看《骗分导论》相关介绍（然而那个贪心不是骗分算法哦）。
代码：
/**************************************************************
Problem: 1034
User: danihao123
Language: C++
Result: Accepted
Time:256 ms
Memory:1604 kb
****************************************************************/
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=100001;
int a[maxn],b[maxn];
int n;
inline int solve(int *A,int *B){
register int L1=1,R1=n,L2=1,R2=n,ans=0;
while(L1<=R1 && L2<=R2){
if(A[L1]>B[L2]){
ans+=2;
L1++;
L2++;
}else{
if(A[R1]>B[R2]){
ans+=2;
R1--;
R2--;
}else{
if(A[L1]==B[R2])
ans++;
L1++;
R2--;
}
}
}
return ans;
}
int main(){
register int i,ans;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
sort(a+1,a+1+n);
sort(b+1,b+1+n);
printf("%d %d\n",solve(a,b),2*n-solve(b,a));
return 0;
}
[BZOJ 1036]树的统计
终于A了这题了！
树剖大水题~
然而zzs这种蒟蒻还是要交很多次才过：
