【BZOJ 4817】[SDOI2017] 树点涂色

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4817

解题报告

我们发现涂色可以看作LCT的access操作
然后权值就是到根的虚边数

于是用LCT来维护颜色
用线段树配合DFS序来支持查询
时间复杂度:$O(n \log^2 n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = N << 1;
const int LOG = 20;

int n, m, head[N], nxt[M], to[M]; 
int in[N], ot[N], dep[N], num[N], ff[N][LOG];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline int LCA(int u, int v) {
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	for (int j = LOG - 1; ~j; j--) {
		if (dep[ff[u][j]] >= dep[v]) {
			u = ff[u][j];
		}
	}
	if (u == v) {
		return u;
	}
	for (int j = LOG - 1; ~j; j--) {
		if (ff[u][j] != ff[v][j]) {
			u = ff[u][j];
			v = ff[v][j];
		}
	}
	return ff[u][0];
}

class SegmentTree{
	int root, ch[M][2], tag[M], mx[M];
public:
	inline void init() {
		build(root, 1, n);
	}
	inline void modify(int l, int r, int d) {
		modify(root, 1, n, l, r, d);
	}
	inline int query(int l, int r = -1) {
		return query(root, 1, n, l, r >= 0? r: l);
	}
private:
	inline void PushDown(int w) {
		if (tag[w]) {
			int ls = ch[w][0], rs = ch[w][1];
			mx[ls] += tag[w];
			mx[rs] += tag[w];
			tag[ls] += tag[w];
			tag[rs] += tag[w];
			tag[w] = 0;
		}
	}
	inline int query(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return mx[w];
		} else {
			PushDown(w);
			int mid = l + r + 1 >> 1, ret = 0;
			if (L < mid) {
				ret = max(ret, query(ch[w][0], l, mid - 1, L, R));
			}
			if (mid <= R) {
				ret = max(ret, query(ch[w][1], mid, r, L, R));
			}
			return ret;
		}
	}
	inline void modify(int w, int l, int r, int L, int R, int d) {
		if (L <= l && r <= R) {
			tag[w] += d;
			mx[w] += d;
		} else {
			PushDown(w);
			int mid = l + r + 1 >> 1;
			if (L < mid) {
				modify(ch[w][0], l, mid - 1, L, R, d);
			}
			if (mid <= R) {
				modify(ch[w][1], mid, r, L, R, d);
			}
			mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]);
		}
	}
	inline void build(int &w, int l, int r) {
		static int cnt = 0;
		w = ++cnt;
		if (l == r) {
			mx[w] = dep[num[l]];
		} else {
			int mid = l + r + 1 >> 1;
			build(ch[w][0], l, mid - 1);
			build(ch[w][1], mid, r);
			mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]);
		}
	}
}SGT;

class LinkCutTree{
	int ch[N][2], fa[N];
public:
	inline void SetFather(int w, int f) {
		fa[w] = f;
	}
	inline void access(int x) {
		for (int last = 0; x; last = x, x = fa[x]) {
			splay(x);
			if (fa[x]) {
				int p = GetMin(x);
				SGT.modify(in[p], ot[p], -1);
			}
			if (ch[x][1]) {
				int p = GetMin(ch[x][1]);
				SGT.modify(in[p], ot[p], 1);
			}
			ch[x][1] = last;
		}
	}
private:
	inline bool IsRoot(int x) {
		return !fa[x] || (ch[fa[x]][0] != x && ch[fa[x]][1] != x);
	}
	inline int GetMin(int x) {
		return ch[x][0]? GetMin(ch[x][0]): x;
	}
	inline void splay(int x) {
		for (int f, ff; !IsRoot(x); ) {
			f = fa[x], ff = fa[f];
			if (IsRoot(f)) {
				rotate(x);
			} else {
				if ((ch[ff][0] == f) ^ (ch[f][0] == x)) {
					rotate(x);
					rotate(x);
				} else {
					rotate(f);
					rotate(x);
				}
			}
		}
	}
	inline void rotate(int x) {
		int f = fa[x], t = ch[f][1] == x;
		fa[x] = fa[f];
		if (!IsRoot(f)) {
			ch[fa[f]][ch[fa[f]][1] == f] = x;
		}
		ch[f][t] = ch[x][t ^ 1];
		fa[ch[x][t ^ 1]] = f;
		ch[x][t ^ 1] = f;
		fa[f] = x;
	}
}LCT;

inline void DFS(int w, int f) {
	static int ID = 0;
	LCT.SetFather(w, f);
	ff[w][0] = f;
	dep[w] = dep[f] + 1;
	num[in[w] = ++ID] = w;
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
		}
	}
	ot[w] = ID;
}	

int main() {
	n = read(); m = read();
	for (int i = 1; i < n; i++) {
		AddEdge(read(), read());
	}
	DFS(1, 0);
	for (int j = 1; j < LOG; j++) {
		for (int i = 1; i <= n; i++) {
			ff[i][j] = ff[ff[i][j - 1]][j - 1];
		}
	}
	SGT.init();
	for (int i = 1; i <= m; i++) {
		int opt = read();
		if (opt == 1) {
			LCT.access(read());
		} else if (opt == 2) {
			int u = read(), v = read(), lca = LCA(u, v);
			printf("%d\n", SGT.query(in[u]) + SGT.query(in[v]) - 2 * SGT.query(in[lca]) + 1);
		} else {
			int x = read();
			printf("%d\n", SGT.query(in[x], ot[x]));
		}
	}
	return 0;
}

【BZOJ 3881】[COCI2015] Divljak

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3881
神犇题解:http://trinkle.is-programmer.com/2015/6/30/bzoj-3881.100056.html

解题报告

考虑把Alice的串建成AC自动机
那么每一次用Bob的串去匹配就是Fail树上一些树链的并
这个用BIT+虚树无脑维护一下就可以了

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 2000009;
const int LOG = 26;
const int SGZ = 26;

int in[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

class Ac_Automaton{
int root, cnt, ch[N][SGZ], fail[N], pos[N], dep[N];
int head[N], to[N], nxt[N], ot[N], fa[N][LOG];
class FenwickTree{
int mx, sum[N];
public:
	inline void init(int nn) {
		mx = nn;
	}
	inline void modify(int p, int d) {
		for (int i = p; i <= mx; i += lowbit(i)) {
			sum[i] += d;
		}
	}
	inline int query(int l, int r) {
		int ret = 0;
		for (int i = l - 1; i > 0; i -= lowbit(i)) {
			ret -= sum[i];
		}
		for (int i = r; i; i -= lowbit(i)) {
			ret += sum[i];
		}
		return ret;
	}
private:
}bit;
public:
	inline void insert(char *s, int nn, int id) {
		int w = root;
		for (int i = 1; i <= nn; i++) {
			int cc = s[i] - 'a';
			if (!ch[w][cc]) {
				ch[w][cc] = ++cnt;
			}
			w = ch[w][cc];
		} 
		pos[id] = w;
	}
	inline void build() {
		static queue<int> que;
		for (int i = 0; i < SGZ; i++) {
			if (ch[root][i]) {
				que.push(ch[root][i]);
			}
		}
		for (; !que.empty(); que.pop()) {
			int w = que.front();
			AddEdge(fail[w], w);
			for (int i = 0; i < SGZ; i++) {
				if (!ch[w][i]) {
					ch[w][i] = ch[fail[w]][i];
				} else {
					que.push(ch[w][i]);
					fail[ch[w][i]] = ch[fail[w]][i];
				}
			}
		}
		DFS(0, 0);
		for (int j = 1; j < LOG; j++) {
			for (int i = 0; i <= cnt; i++) {
				fa[i][j] = fa[fa[i][j - 1]][j - 1];
			}
		}
		bit.init(cnt + 1);
	} 
	inline void match(char *s, int nn) {
		static vector<int> vt[N];
		static int que[N], stk[N], vis[N]; 
		int qtot = 0, stot = 0, vtot = 0;
		que[++qtot] = root;
		for (int i = 1, w = root; i <= nn; i++) {
			w = ch[w][s[i] - 'a'];
			que[++qtot] = w;
		}
		sort(que + 1, que + 1 + qtot);
		qtot = unique(que + 1, que + 1 + qtot) - que - 1;
		sort(que + 1, que + 1 + qtot, cmp);
		for (int i = 1; i <= qtot; i++) {
			if (stot) {
				int lca = LCA(que[i], stk[stot]);
				for (; stot && dep[stk[stot]] > dep[lca]; --stot) {
					if (stot > 1 && dep[stk[stot - 1]] >= dep[lca]) {
						vt[stk[stot - 1]].push_back(stk[stot]);
					} else {
						vt[lca].push_back(stk[stot]);
					}
				}
				if (stot && stk[stot] != lca) {
					stk[++stot] = lca;
					vis[++vtot] = lca;
				}
			} 
			stk[++stot] = que[i];
			vis[++vtot] = que[i];
		}
		for (; stot > 1; --stot) {
			vt[stk[stot - 1]].push_back(stk[stot]);
		}
		update(root, vt);
		for (int i = 1; i <= vtot; i++) {
			vt[vis[i]].clear();
		}
	}
	inline int query(int id) {
		return bit.query(in[pos[id]], ot[pos[id]]);
	}
private:
	inline void update(int w, vector<int> *vt) {
		for (int i = 0; i < (int)vt[w].size(); i++) {
			bit.modify(in[w], -1);
			bit.modify(in[vt[w][i]], 1);
			update(vt[w][i], vt);
		}
	}
	inline int LCA(int a, int b) {
		if (dep[a] < dep[b]) {
			swap(a, b);
		}
		for (int j = SGZ - 1; ~j; j--) {
			if (dep[fa[a][j]] >= dep[b]) {
				a = fa[a][j];
			}
		}
		if (a == b) {
			return a;
		}
		for (int j = SGZ - 1; ~j; j--) {
			if (fa[a][j] != fa[b][j]) {
				a = fa[a][j];
				b = fa[b][j];
			}
		}
		return fa[a][0];
	} 
	static bool cmp(int a, int b) {
		return in[a] < in[b];
	}
	inline void DFS(int w, int f) {
		static int tt = 0;
		in[w] = ++tt;
		dep[w] = dep[fa[w][0] = f] + 1;
		for (int i = head[w]; i; i = nxt[i]) {
			DFS(to[i], w);
		}
		ot[w] = tt;
	}
	inline void AddEdge(int u, int v) {
		static int E = 1;
		to[++E] = v; nxt[E] = head[u]; head[u] = E;
	}
}ac;

int main() {
	static char ss[N];
	int n = read();
	for (int i = 1; i <= n; i++) {
		scanf("%s", ss + 1);
		int len = strlen(ss + 1);
		ac.insert(ss, len, i);
	}
	ac.build();
	int m = read();
	for (int i = 1; i <= m; i++) {
		if (read() == 1) {
			scanf("%s", ss + 1);
			int len = strlen(ss + 1);
			ac.match(ss, len);
		} else {
			printf("%d\n", ac.query(read()));
		}
	}
	return 0;
}

【BZOJ 3672】[NOI2014] 购票

解题报告

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3672
神犇题解:http://blog.csdn.net/lych_cys/article/details/51317809

解题报告

一句话题解:树上CDQ分治

先推一推式子,发现可以斜率优化
于是我们可以用树链剖分做到$O(n \log^3 n)$
或者也可以用KD-Tree配合DFS序做到$O(n^{1.5} \log n)$

我们进一步观察,使单纯的DFS序不能做的地方在于凸包是动态的,查询也是动态的且限制了横坐标的最小值
考虑分治的话,我们按横坐标的限制排序,然后边查询边更新凸包就可以了
总的时间复杂度:$O(n \log^2 n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;
const int M = N << 1;
const LL INF = 6e18;

int n, head[N], nxt[M], to[M], fa[N];
LL q[N], p[N], len[N], dep[N], f[N];

struct Point{
	LL x, y, id, range;
	inline Point() {
	}
	inline Point(LL a, LL b, LL c, LL d):x(a), y(b), id(c), range(d) {
	}
	inline bool operator < (const Point &P) const {
		return x > P.x || (x == P.x && y > P.y);
	}
	inline Point operator - (const Point &P) {
		return Point(x - P.x, y - P.y, 0, 0);
	}
	inline double operator * (const Point &P) {
		return (double)x * P.y - (double)y * P.x;
	}
	inline double slope(const Point &P) {
		return (double)(y - P.y) / (x - P.x);
	}
	static bool update(const Point &P1, const Point &P2) {
		return P1.range > P2.range;
	}
};

inline LL read() {
	char c = getchar(); LL ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; 
	to[++E] = u; nxt[E] = head[v]; head[v] = E; 
}

class DivideAndConquer{
int sz[N], vis[N];
public:	
	inline void solve(int w, int universe) {
		int top = w;
		vis[w = FindRoot(w, universe)] = 1;
		if (fa[w] && !vis[fa[w]]) {
			solve(top, universe - sz[w]);
		}
		vector<Point> cvx;
		for (int nw = fa[w]; dep[nw] >= dep[top]; nw = fa[nw]) {
			cvx.push_back(Point(dep[nw], f[nw], nw, dep[nw] - len[nw]));
		}
		vector<Point> que;
		que.push_back(Point(dep[w], 0, w, dep[w] - len[w]));
		for (int i = head[w]; i; i = nxt[i]) {
			if (dep[to[i]] > dep[w] && !vis[to[i]]) {
				DFS(to[i], w, que);
			}	
		}	
		
		sort(que.begin(), que.end(), Point::update);
		sort(cvx.begin(), cvx.end());
		for (int i = 0, j = 0, tot = 0; i < (int)que.size(); i++) {
			for (; j < (int)cvx.size() && cvx[j].x >= que[i].range; j++) {
				for (; tot > 1 && (cvx[tot - 1] - cvx[tot - 2]) * (cvx[j] - cvx[tot - 2]) >= 0; --tot);
				cvx[tot++] = cvx[j];
			}
			int ret = tot - 1, l = 0, r = tot - 2, mid, k = que[i].id;
			while (l <= r) {
				mid = l + r >> 1;
				if (cvx[mid].slope(cvx[mid + 1]) <= p[k]) {
					ret = mid;
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}
			if (ret >= 0) {
				f[k] = min(f[k], cvx[ret].y + (dep[k] - cvx[ret].x) * p[k] + q[k]);
			}
		}
		for (int i = 0, j; i < (int)que.size(); i++) {
			if (j = que[i].id, que[i].range <= dep[w]) {
				f[j] = min(f[j], f[w] + (dep[j] - dep[w]) * p[j] + q[j]);
			}
		}
		que.clear();
		cvx.clear();
	
		for (int i = head[w]; i; i = nxt[i]) {
			if (dep[to[i]] > dep[w] && !vis[to[i]]) {
				solve(to[i], sz[to[i]]);
			}
		}	
	}	
private:
	inline int FindRoot(int w, int universe) {
		int ret = 0, ans;
		FindRoot(w, w, universe, ret, ans);
		return ret;
	}	
	inline void FindRoot(int w, int f, int universe, int &ret, int &ans) {
		int mx = 1; sz[w] = 1;
		for (int i = head[w]; i; i = nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				FindRoot(to[i], w, universe, ret, ans);
				sz[w] += sz[to[i]];
				mx = max(mx, sz[to[i]]);
			}
		}
		mx = max(mx, universe - sz[w]);
		if (!ret || mx < ans) {
			ans = mx;
			ret = w;
		}
	}
	inline void DFS(int w, int f, vector<Point> &ret) {
		ret.push_back(Point(dep[w], 0, w, dep[w] - len[w]));
		for (int i = head[w]; i; i = nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				DFS(to[i], w, ret);
			}
		}
	}
}DAC;

int main() {
	n = read(); read();
	for (int i = 2; i <= n; i++) {
		fa[i] = read();
		LL c = read(); AddEdge(fa[i], i);
		p[i] = read(); q[i] = read();
		len[i] = read();
		dep[i] = dep[fa[i]] + c;
	}
	fill(f, f + N, INF);
	f[1] = 0; dep[0] = -1;
	DAC.solve(1, n);
	for (int i = 2; i <= n; i++) {
		printf("%lld\n", f[i]);
	}
	return 0;
}

【日常小测】学外语

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/07/NOI2017-matthew99.pdf

解题报告

从$i$向$a_i$连边
不难发现这题就是求一个基环树森林与自身同构的情况
这个我们可以用$Hash$来搞一搞

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000009;
const int MOD = 1000000007;
const int INF = 2e9;

int n, E, ans, head[N], nxt[N], to[N];
int inv[N], pw[N], ipw[N], pw23[N], R1[N], R2[N];
int pre[N], dep[N], in[N], deg[N], vis[N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar()) {
		f = c == '-'? -1: 1;
	}
	for (; '0' <= c && c <= '9'; c = getchar()) {
		ret = ret * 10 + c - '0';
	}
	return ret * f;
}

inline int Pow(int w, int t) {
	int ret = 1;
	for (; t; t >>= 1, w = (LL)w * w % MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		}
	}
	return ret;
}

inline void AddEdge(int u, int v) {
	in[v]++; deg[v]++; pre[u] = v;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline void mrk(int w) {
	vis[w] = 1;
	if (--in[pre[w]] == 0) {
		mrk(pre[w]);
	}
}

inline int cal_node(int w) {
	int ret = R2[deg[w]];
	vector<int> arr;
	for (int i = head[w]; i; i = nxt[i]) {
		if (!in[to[i]]) {
			dep[to[i]] = dep[w] + 1;
			int tmp = cal_node(to[i]);
			arr.push_back(tmp);
			ret = (ret + (LL)R1[dep[w]] * tmp) % MOD;
		}
	}
	sort(arr.begin(), arr.end());
	for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) {
		for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j);
		ans = (LL)ans * ipw[j - i + 1] % MOD;
	}
	return (LL)ret * ret % MOD;
}

inline int cal_cir(int w) {
	vector<int> node, arr;
	while (!vis[w]) {
		vis[w] = 1;
		node.push_back(w);
		for (int i = head[w]; i; i = nxt[i]) {
			if (in[to[i]]) {
				w = to[i];
				break;
			}
		}
	}
	for (int i = 0; i < (int)node.size(); i++) {
		dep[node[i]] = 6;
		arr.push_back(cal_node(node[i]));
	}
	int sta = 0, cnt = 1;
	for (int i = 0; i < (int)node.size(); i++) {
		sta = (sta + (LL)pw23[i] * arr[i]) % MOD;
	} 
	int ret = (LL)sta * pw23[n] % MOD;
	for (int i = 1, cur = sta; i < (int)node.size(); i++) {
		cur = (cur + (LL)arr[i - 1] * (pw23[i - 1 + node.size()] - pw23[i - 1])) % MOD;
		ret = min(ret, int((LL)cur * pw23[n - i] % MOD));
		cnt += ((cur = (cur + MOD) % MOD) == (LL)sta * pw23[i] % MOD);
	}
	ans = (LL)ans * inv[cnt] % MOD;
	return ret;
}

int main() {
	srand(19991216);
	inv[0] = pw[0] = ipw[0] = pw23[0] = 1;
	R1[0] = rand(); R2[0] = rand();
	for (int i = 1; i < N; i++) {
		pw[i] = (LL)pw[i - 1] * i % MOD;
		pw23[i] = pw23[i - 1] * 131ll % MOD;
		inv[i] = Pow(i, MOD - 2);
		ipw[i] = Pow(pw[i], MOD - 2);
		R1[i] = rand(); R2[i] = rand();
	}
	
	for (int T = read(); T; T--) {
		memset(head, 0, sizeof(head));
		memset(deg, 0, sizeof(deg));
		memset(vis, 0, sizeof(vis));
		memset(in, 0, sizeof(in));
		E = 0; ans = 1;
		
		n = read();
		for (int i = 1; i <= n; i++) {
			AddEdge(i, read());
		}	
		for (int i = 1; i <= n; i++) {
			if (!in[i] && !vis[i]) {
				mrk(i);
			}
		}
		vector<int> arr;
		for (int i = 1; i <= n; i++) {
			if (in[i] && !vis[i]) {
				arr.push_back(cal_cir(i));
			}
		}
		sort(arr.begin(), arr.end());
		for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) {
			for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j);
			ans = (LL)ans * ipw[j - i + 1] % MOD;
		}
		ans = ((LL)ans * pw[n] - 1) % MOD;
		printf("%d\n", (ans + MOD) % MOD);
	}
	return 0;
}

【BZOJ 4883】[Lydsy2017年5月月赛] 棋盘上的守卫

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4883
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/05/ludsy_may_contest_solution.pdf

解题报告

把行和列看成点,格子看成边
那么一个$n$个点的连通块需要$n$条边
于是用$Kruskal$做一个基环树森林就可以了
时间复杂度:$O(nm \log nm)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300000;

struct Edge{
	int u, v, c;
	bool operator < (const Edge &ee) const {
		return c < ee.c;
	}
}e[N];
int n, m, tot, cir[N], fa[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int find(int x) {
	return x == fa[x]? x: fa[x] = find(fa[x]);
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	n = read(); m = read();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			e[++tot].c = read();
			e[tot].u = i;
			e[tot].v = n + j;
		}
	}
	sort(e + 1, e + 1 + tot);
	for (int i = 1; i <= n + m; i++) {
		fa[i] = i;
	}
	LL ans = 0;
	for (int i = 1; i <= tot; i++) {
		int u = e[i].u, v = e[i].v;
		int fu = find(u), fv = find(v);
		if (cir[fu] && cir[fv]) {
			continue;
		} else if (fu != fv) {
			fa[fv] = fu;
			cir[fu] |= cir[fv];
		} else if (!cir[fu]) {
			cir[fu] = 1;
		}
		ans += e[i].c;
	}
	printf("%lld\n", ans);
	return 0;
}

【BZOJ 4878】[Lydsy2017年5月月赛] 挑战NP-Hard

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4878

解题报告

我们搞出$DFS$生成树
如果树高大于$k$,那么显然可以找出长度为$k$的简单路径
如果树高$\le k$的话,因为非树边一定是返祖边,所以把深度作为颜色就可以$k$染色了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1009;
const int M = 20009;

int n,m,k,E,head[N],nxt[M],to[M];
int DONE,fa[N],dep[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void AddEdge(int u, int v) {
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void DFS(int w, int f) {
	dep[w] = dep[f] + 1;
	fa[w] = f;
	if (dep[w] > k) {
		DONE = 1;
		printf("path ");
		for (; 1; w = fa[w]) {
			printf("%d ", w);
			if (w == fa[w]) {
				break;
			}
		}
		cout<<endl;
	} else {
		for (int i = head[w]; i && !DONE; i = nxt[i]) {
			if (!dep[to[i]]) {
				DFS(to[i], w);
			}
		}
	}
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	for (int T = read(); T; T--) {
		memset(head, 0, sizeof(head));
		n = read(); m = read(); 
		k = read(); E = DONE = 0;
		for (int i = 1; i <= m; i++) {
			AddEdge(read(), read());
		}
		memset(dep, 0, sizeof(dep));
		for (int i = 1; i <= n && !DONE; ++i) {
			if (!dep[i]) {
				DFS(i, i);
			}
		}
		if (!DONE) {
			printf("color ");
			for (int i = 1; i <= n; ++i) {
				printf("%d ", dep[i]);
			}
			cout<<endl;
		}
	} 
	return 0;
}

【TopCoder SRM713】DFSCount

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14588&rd=16882

题目大意

给定一个$n(n \le 14)$的简单无向图,问$DFS$序总共可能有多少种不同情况

解题报告

这是一个非常妙妙的$DP$
考虑定义$f_{i,j}$表示当前在第$i$个点,已经走过的点压成二进制状态为$j$
但我们发现这样无法实现$DFS$模拟当中的退回操作

但我们考虑一下$DFS$树:这货是没有横叉边的,只有返祖边
这意味着我们如果决定朝一个方向走,那么一定是把那一个连通块走完才会退回来
于是我么可以不一步一步转移,我们可以把一整块连通块一起转移,这样就不需要模拟$DFS$的回退操作了

至于这份代码是:$O(n^2 2^n)$的
实现得精细一点可以做到$O(n 2^n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
int n,id[15];
bool g[15][15],vis[15];
LL f[15][17000],pw[15],pol[15];

class DFSCount {
    public:
    	long long count(vector<string> G) {
    		pw[0] = 1;
    		for (int i=1;i<=14;i++) {
				pw[i] = pw[i-1] * i;
			}
    	    n = G.size();
    	    for (int i=0;i<n;i++) {
				for (int j=0;j<n;j++) {
					if (G[i][j] == 'Y') g[i][j] = 1;
					else g[i][j] = 0;
				}
			}
    	    memset(f, 0, sizeof(f));
			for (int i=0;i<n;i++) {
				f[i][(1<<n)-1] = 1;
			}
			for (int sta=(1<<n)-2;sta>0;sta--) {
				for (int i=0;i<n;i++) {
					if (!(sta&(1<<i))) continue;
					for (int j=0;j<n;j++) {
						vis[j] = (sta & (1 << j));
					}
					int cnt = 0;
					for (int j=0;j<n;j++) {
						if (g[i][j] && !(sta&(1<<j))) {
							if (!vis[j]) {
								DFS(j, ++cnt);
								pol[cnt] = 0;
							}
							pol[id[j]] += f[j][(1<<j)|sta];
						}
					}
					f[i][sta] = pw[cnt];
					for (int j=1;j<=cnt;j++) {
						f[i][sta] *= pol[j];
					}
				}
			}
			LL ret = 0;
			for (int i=0;i<n;i++) {
				ret += f[i][1<<i];
			}
			return ret;
   		}
   	private:
   		void DFS(int w, int ID) {
			vis[w] = 1; 
			id[w] = ID;
			for (int i=0;i<n;i++) {
				if (g[w][i] && !vis[i]) {
					DFS(i, ID);
				} 
			}   
		}
};

【Codeforces 797D】Broken BST

相关链接

题目传送门:http://codeforces.com/contest/797/problem/D

解题报告

之前做过类似的题:https://oi.qizy.tech/?p=298
大概就是说,排序之后,每个点的左右子树切换至多发生一次
于是用基排来离散化的话,时间复杂度就是:$O(n)$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;

int n,rt,is_rt[N],val[N],ch[N][2],TOT[N];
int tot,_hash[N],cnt[N],dep[N],vout;
set<pair<int,int> > id[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

void dfs(int w, int f) {
	dep[w] = dep[f] + 1;
	if (ch[w][1]) dfs(ch[w][1], w);
	if (ch[w][0]) dfs(ch[w][0], w);
}

void add(int w, int sta) {
	if (w <= 0) return;
	id[val[w]].insert(make_pair(dep[w], w)); 
	cnt[val[w]]++;
	if (val[w] > sta) add(ch[w][0], sta);
	else add(ch[w][1], sta);
}

void del(int w, int sta) {
	if (w <= 0) return;
	id[val[w]].erase(make_pair(dep[w], w));
	cnt[val[w]]--;
	if (val[w] > sta) del(ch[w][0], sta);
	else del(ch[w][1], sta);
}

int main() {
	n = read();
	for (int i=1,l,r;i<=n;i++) {
		val[i] = read(); _hash[++tot] = val[i];
		if ((l = read()) != -1) ch[i][0] = l, is_rt[l] = 1;
		if ((r = read()) != -1) ch[i][1] = r, is_rt[r] = 1;
	}
	for (int i=1;i<=n;i++) if (!is_rt[i]) {rt = i; break;}
	dfs(rt, rt);
	sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=n;i++) val[i] = lower_bound(_hash+1, _hash+1+tot, val[i]) - _hash, TOT[val[i]]++;
	
	add(rt, 1);
	if (!cnt[1]) vout += TOT[1];
	for (int i=2,w;i<=tot;i++) {
		if (id[i].size() > 0) {
			auto tmp = id[i].begin();
			w = tmp->second;
			del(w, i-1);
			add(w, i);
		}
		if (cnt[i] == 0) vout += TOT[i];
	}	
	printf("%d\n",vout);
	return 0;
}

【BZOJ 3451】Tyvj1953 Normal

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3451
神犇题解:http://wyfcyx.is-programmer.com/posts/74735.html

解题报告

考虑一个点$u$,如果点分到点$v$的时候会产生贡献
那么点分$v$的时候,$v \to u$这个路径上还没有其他点被点分
换一句话来讲,点$v$应该是$v \to u$这条路径上第一个被点分的点
因为每一个点被选的概率一样,所以贡献的概率是$\frac{1}{dis_{u \to v} + 1}$
于是最后答案就是$\sum\limits_{u,v \in [1,n]}{\frac{1}{dis_{u \to v}+1}}$

然后这个东西我们可以使用点分治加上FFT来解决
具体来讲就是在点分的时候统计$dis_{u \to v}=x$的方案数,然后计入答案
时间复杂度:$O(n \log^2 n)$

—————————— UPD 2017.4.11 ————————————
找到这题的序列版了:http://www.lydsy.com/JudgeOnline/problem.php?id=2769
在具体的做法方面,用分个块,然后块内暴力,块间FFT即可

【CodeChef GRAPHCNT】[May Challenge 2015] Counting on a directed graph

相关链接

题目传送门:https://www.codechef.com/problems/GRAPHCNT
数据生成器:http://paste.ubuntu.com/24319212/
神犇题解Ⅰ:http://blog.csdn.net/a710128/article/details/49913553
神犇题解Ⅱ:http://www.cnblogs.com/meowww/p/6475952.html

解题报告

就是支配树的板题?

我们可以用Lengauer Tarjan算法在$O(n \alpha (n))$的时间复杂度内解决这个问题
也可以求出所有的半支配点,然后用灭绝树来搞,时间复杂度:$O(n \log n)$
另外之前我还看到一种非常鬼畜地LCT+灭绝树地做法,时间复杂度跑起来像:$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 1500009;

int n,m;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class Dominator_Tree{
	int dom[N],pre[N],head[N],nxt[M],to[M],que[N],anc[N];
	int dfs_cnt,dfn[N],idom[N],semi[N],bst[N],ufs[N],sz[N];
	public: 
		inline void AddEdge(int u, int v) {
			AddEdge(head, u, v);
			AddEdge(pre, v, u);	
		}
		inline void build() {
			DFS(1);
			for (int i=dfs_cnt,w;w=que[i],i>1;i--) {
				for (int j=pre[w];j;j=nxt[j]) {
					if (dfn[to[j]]) {
						update(to[j]);
						if (dfn[semi[bst[to[j]]]] < dfn[semi[w]])
							semi[w] = semi[bst[to[j]]];
					}
				}
				AddEdge(dom, semi[w], w);
				ufs[w] = anc[w]; w = que[i-1];
				for (int j=dom[w];j;j=nxt[j]) {
					update(to[j]);
					if (semi[bst[to[j]]] == w) idom[to[j]] = w;
					else idom[to[j]] = bst[to[j]];
				}
			}
			for (int i=2,w;w=que[i],i<=dfs_cnt;i++)
				idom[w] = ((idom[w] == semi[w])? idom[w]: idom[idom[w]]);
		}
		inline LL solve() {
			LL ret = dfs_cnt * (dfs_cnt - 1ll) / 2ll; 
			for (int i=dfs_cnt,w;w=que[i],i>1;i--) { 
				if (++sz[w], idom[w] != 1) sz[idom[w]] += sz[w];
				else ret -= (sz[w] - 1ll) * sz[w] / 2ll;
			} return ret;
		}
	private:
		inline void AddEdge(int *arr, int u, int v) {
			static int E = 1; 
			to[++E] = v; nxt[E] = arr[u]; arr[u] = E;
		}	
		void DFS(int w) {
			dfn[w] = ++dfs_cnt; que[dfs_cnt] = w;
			bst[w] = semi[w] = ufs[w] = w;
			for (int i=head[w];i;i=nxt[i]) 
				if (!dfn[to[i]]) anc[to[i]] = w, DFS(to[i]);
		}
		int update(int w) {
			if (ufs[w] == w) return w;
			int tmp = update(ufs[w]);
			if (dfn[semi[bst[ufs[w]]]] < dfn[semi[bst[w]]])
				bst[w] = bst[ufs[w]];
			return ufs[w] = tmp;
		}
}DMT;

int main() {
	n = read(); m = read();
	for (int i=1,u,v;i<=m;i++) {
		u = read(); v = read();
		DMT.AddEdge(u, v);
	}
	DMT.build();
	cout<<DMT.solve();
	return 0;
}