【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;
}

【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);
				} 
			}   
		}
};

【BZOJ 4182】Shopping

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4182
神犇题解:http://www.cnblogs.com/clrs97/p/4676134.html

解题报告

这个是一个多重背包,于是我们定义$f_{i,j}$为走到第$i$个点,花费$j$元的最大收益
我们先搞出一个DFS序,现在对于点$i$我们可以选或不选
若选,那么我们转移到DFS序的下一个去
若不选,那么我们需要跳过他的整个子树——这在DFS序上是一段连续的区间
于是我们就可以在$O(nm \log d)$的时间复杂度内解决这个问题了

另外Claris的点分的做法也非常好玩啊
通用性还要更强一点,提供了一种新的思路

—————————— UPD 2017.3.19 ——————————
这题今天写了写代码,似乎不能直接DP,会有一系列问题
将上述DP套个点分就没有问题了,不过套点分的话,就直接像Claris那么做就好啦
总之复杂度似乎还是只能做到$O(nm \log n \log m)$

【Codeforces 782E】Underground Lab

相关链接

题目传送门:http://codeforces.com/contest/782/problem/E

吐槽

没有看懂题,于是跑去问Menci题意
结果Menci先说做法,后说题意 _(:з」∠)_
强行把我带上了紫 *★,°*:.☆( ̄▽ ̄)/$:*.°★* 。

解题报告

我们发现这个$\lceil \ \rceil$和$2n$非常妙啊!
于是乎,我们先搞出欧拉序,然后分成$k$段输出就可以了

Code

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

const int N = 400009;

int n,m,k,tot,vis[N],head[N],nxt[N],to[N],que[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 Add_Edge(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;
}

void DFS(int w) {
	vis[w] = 1; que[++tot] = w;
	for (int i=head[w];i;i=nxt[i]) {
		if (!vis[to[i]]) {
			DFS(to[i]);
			que[++tot] = w;
		}
	} 
}

int main() {
	n = read(); m = read(); k = read();
	for (int i=1;i<=m;i++) {
		Add_Edge(read(), read());
	}
	DFS(1);
	for (int i=1,cur=1,c=ceil(2.0*n/k);i<=k;i++) {
		if (cur > tot) puts("1 1"); 
		else {
			if (tot-cur+1 >= c) {
				printf("%d ",c);
				for (int j=1;j<=c;j++) printf("%d ",que[cur++]);
				puts("");
			} else {
				printf("%d ",tot-cur+1);
				for (int j=cur;j<=tot;j++) printf("%d ",que[j]);
				puts("");
			}
		}
	}
	return 0;
}

【日常小测】链上求和

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/03/3764237472378947264.png
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/03/4876274224.jpg

解题报告

这题就是暴力写出来之后,发现可以直接维护一个东西
于是维护一个子树和,然后支持一下换根的操作就可以辣!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int N = 100009;
const int M = N << 1;
const int MOD = 1000000007;
  
int n,vout,head[N],to[M],nxt[M],val[N];
int tot,fa[N],yzq_in[N],yzq_out[N],sz[N];
struct Query{int v,id;}q[N];
  
class Fenwick_Tree{
    #define lowbit(x) ((x)&-(x))
    public:
        int sum[N],SUM;
        inline void modify(int p, int v) {
            for (int i=p;i<=n;i+=lowbit(i)) sum[i] = (sum[i] + v) % MOD;
            SUM = (SUM + v) % MOD;
        } 
        inline void modify(int l, int r, int v) {
            for (int i=r;i;i-=lowbit(i)) sum[i] = (sum[i] + v) % MOD;
            for (int i=l-1;i;i-=lowbit(i)) sum[i] = (sum[i] - v) % MOD;
        }
        inline int query(int l, int r) {
            int ret = 0;
            for (int i=r;i;i-=lowbit(i)) ret = (ret + sum[i]) % MOD;
            for (int i=l-1;i;i-=lowbit(i)) ret = (ret - sum[i]) % MOD;
            return (ret + MOD) % MOD;
        }
        inline int query(int p) {
            int ret = 0;
            for (int i=p;i<=n;i+=lowbit(i)) ret = (ret + sum[i]) % MOD;
            return (ret + MOD) % MOD;
        }
}BIT,BIT2,BIT3;
  
inline int read() {
    char c=getchar(); int ret=0,f=1;
    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 Add_Edge(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 bool cmp(const Query &A, const Query &B) {
    return A.v < B.v || (A.v == B.v && A.id < B.id);
}
  
void DFS(int w, int f) {
    fa[w] = f; yzq_in[w] = ++tot; sz[w] = 1;
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            DFS(to[i], w);
            sz[w] += sz[to[i]];
        }
    }
    yzq_out[w] = tot;
}   
  
inline void solve(int w) {
    int ret = 0; LL cur=1,s1;
    for (int i=head[w],s,c;i;i=nxt[i]) {
        if (to[i] == fa[w]) {
            s = (BIT.SUM - BIT.query(yzq_in[w], yzq_out[w])) % MOD; 
            s1 = BIT3.query(yzq_in[w]);
            c = BIT2.query(yzq_in[w]);
            s = (s - s1 + (LL)c * n) % MOD;
            ret = (ret + (LL)sz[w] * s) % MOD; 
            ret = (ret + (LL)(n - sz[w]) * cur) % MOD;
            cur += n - sz[w];
        } else {
            ret = (ret + (LL)(n-sz[to[i]]) * BIT.query(yzq_in[to[i]], yzq_out[to[i]])) % MOD;
            ret = (ret + (LL)sz[to[i]] * cur) % MOD;
            cur += sz[to[i]];
        }
    }
    vout = (vout + (LL)ret * val[w]) % MOD;
}
 
int main() {
    n = read();
    for (int i=1;i<n;i++) Add_Edge(read(), read());
    for (int i=1;i<=n;i++) val[i] = q[i].v = read(), q[i].id = i;
    DFS(1, 1); sort(q+1, q+1+n, cmp);
    for (int i=1,p,v;i<=n;i++) {
        p = q[i].id;
        solve(p);
        BIT.modify(yzq_in[p], sz[p]);
        BIT2.modify(yzq_in[p], yzq_out[p], 1);
        BIT3.modify(yzq_in[p], yzq_out[p], sz[p]);
        for (int j=head[p],t;j;j=nxt[j]) {
            if ((t=to[j]) != fa[p]) 
                BIT3.modify(yzq_in[t], yzq_out[t], sz[t]);
        }
    }
    printf("%d\n",(vout+MOD)%MOD);
    return 0;
}

【BZOJ 4538】[HNOI2016] 网络

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4538
神犇题解:http://krydom.com/bzoj4538/

解题报告

这题我先说一种怪怪的做法 QwQ
考虑使用主席树,第一维是权值(用BIT搞成后缀和),第二维是DFS序
这样的话,对于询问我们可以在第一维的权值上进行二分
对于每一次二分 $ a$ ,我们可以通过判断覆盖该点的区间个数是否等于所有不小于 $ a$ 的区间个数是否相等

这样话,原问题转化为:在主席树上的区间加减问题
这一块的时空复杂度是 $ O(n{\log ^3}n)$ 的
然后考虑上二分的 $ log$ 这样的话,复杂度就是 $ O(n{\log ^4}n)$ 的
这种做法是自己YY的,感觉很有道理的样子
然而懒得写代码了,也不知道对不对

另外的话,再说一说正解吧!
考虑一条路径,说白了就是查询路径上的点的时候不查到该路径
查询非该路径上的点的时候查询到该路径
这时考虑树链剖分的话,该路径对应的 $ {log(n)}$ 个区间应该忽略,其他部分添加上这个路径的信息
因为是一整块区间抠掉 $ {log(n)}$ 个区间,所以剩余部分也只会有 $ {log(n)}$ 个区间
于是树链剖分暴力搞一搞就可以辣!
时空复杂度比之前的做法应该要稍微优越一点

【HackerRank】Unique Colors

相关链接

题目传送门:https://www.hackerrank.com/challenges/unique-colors
题目大意:http://paste.ubuntu.com/23686184/
官方题解:https://www.hackerrank.com/challenges/unique-colors/editorial

解题报告

Ⅰ.点分治的做法 \(O(n\log (n))\)

先考虑一种较为简单的情况:只有一种颜色
询问有多少对节点间至少存在一个点被染色

直接考虑点分治的做法的话
设当前的分治点为1
定义\({T_i}\)为点i的子树中到1号点的路径上有点被染色的点的数量
定义\({S_i}\)为点i的子树中点的个数

考虑此时对 点3 的贡献:

  1. 点3点1 的简单路径上没有染色点
    那么贡献为\({T_1} – {T_3}\)
  2. 点3点1 的简单路径上有染色点
    那么贡献为\({S_1} – {S_2}\)

这样的话,只有一种颜色的情况就解决了
现在考虑有多种颜色:

不难发现对于一个固定点i,颜色只需要分两类:
1. 到分支点的路径上出现过该颜色
2. 到分治点的路径上没有出现过该颜色

这样的话,我们发现只需要一次DFS就可以解决这个问题
于是就可以使用点分治解决这个问题啦!

Ⅱ. DFS序的做法 \(O(n)\)

先来考虑一个简单一点的版本:假如这货是在序列上
考虑每一种颜色单独处理的话,就是将序列分成几块,每一块的贡献不同
现在重新考虑树上的版本,其实也是把整个树分成好几块
酱紫的话,我们唯一需要解决的就是如何给树上一个连通块统一加上一个数

我们发现我们可以先搞出一个最小的包含“需要更改的连通块”的子树
然后去掉一些子树来删掉多余的部分
子树操作的话,在DFS序上是连续的,于是打差分就好
因为题目的特殊性,不难发现需要删掉的子树总共只会有\(O(n)\)个
于是此题就 \(O(n)\) 辣!

Code

好像两种写法都不是特别好写的样子
于是就不写代码辣!

【BZOJ 4551】[TJOI2016&HEOI2016] 树

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4551
双倍经验:http://www.lydsy.com/JudgeOnline/problem.php?id=3319
神犇题解:http://medalplus.com/?p=1685

题解

  1. 强制在线做法 O(nlogn)
    考虑每一次标记点:只会影响其子树中的点
    所以使用DFS序+线段树就可以辣!

  2. 离线做法 O(nlogn)
    考虑将每一次标记的时间记录到点上
    然后使用倍增LCA的思想向上倍增

  3. 离线做法 O(nα(n))
    考虑离线之后进行逆序操作
    这样的话,操作就变成了删除标记
    这个可以形象地想成:打通了向上走地道路
    于是使用并查集即可
    ps:和BZOJ_3319是一毛一样的

Code

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

const int N = 100000+9;

int head[N],to[N],nxt[N],anc[N],fa[N];
int n,m,tot,opt[N],tag[N],vout[N];
char pat[10];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	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 int find(int w) {
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w], fa[w]=f, w=tmp;
	return f;
}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

void DFS(int w, int last) {
	if (tag[w]) last = fa[w] = w;
	else fa[w] = last;
	for (int i=head[w];i;i=nxt[i]) {
		anc[to[i]] = w;
		DFS(to[i],last);
	}
}

int main(){
	n = read(); m = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		Add_Edge(u,v);
	}
	for (int i=1;i<=m;i++) {
		scanf("%s",pat+1);
		opt[i] = read(); 
		if (pat[1] == 'C') tag[opt[i]]++;
		else opt[i] *= -1;
	}
	tag[1]++; DFS(1,1);
	for (int i=m;i;i--) {
		if (opt[i] > 0) {
			if (!(--tag[opt[i]])) {
				fa[opt[i]] = anc[opt[i]];
			}
		} else {
			vout[++tot] = find(-opt[i]);
		}
	}
	while (tot) printf("%d\n",vout[tot--]); 
	return 0;
}

【BZOJ 4326】[NOIP2015] 运输计划

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

这货的做法就是二分之后,用DFS序判断一下
然而这货居然卡常…….
其实是↑上面这个纸张不会用指针 ╮(╯▽╰)╭
用了加强的流读入才能在UOJ上A
另外前排膜拜Menci,指针用得贼溜:https://oi.men.ci/noip2015-transport/

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

const int N = 300000+9;
const int M = N << 1;

int head[N],to[M],nxt[M],cost[M],sur[M],delta[N];
int dep[N],fa[N][20],in[N],out[N],dis[N],n,m,div_cnt;
struct Query{int u,v,lca,len;}q[N];

namespace fastIO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    #define ll long long
    //fread->read
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
            //{printf("IO error!\n");system("pause");for (;;);exit(0);}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(ll &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(double &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (ch=='.'){
            double tmp=1; ch=nc();
            for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
        }
        if (sign)x=-x;
    }
    inline void read(char *s){
        char ch=nc();
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
        *s=0;
    }
    inline void read(char &c){
        for (c=nc();blank(c);c=nc());
        if (IOerror){c=-1;return;}
    }
    //getchar->read
    inline void read1(int &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (bo)x=-x;
    }
    inline void read1(ll &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (bo)x=-x;
    }
    inline void read1(double &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (ch=='.'){
            double tmp=1;
            for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());
        }
        if (bo)x=-x;
    }
    inline void read1(char *s){
        char ch=getchar();
        for (;blank(ch);ch=getchar());
        for (;!blank(ch);ch=getchar())*s++=ch;
        *s=0;
    }
    inline void read1(char &c){for (c=getchar();blank(c);c=getchar());}
    //scanf->read
    inline void read2(int &x){scanf("%d",&x);}
    inline void read2(ll &x){
        #ifdef _WIN32
            scanf("%I64d",&x);
        #else
        #ifdef __linux
            scanf("%lld",&x);
        #else
            puts("error:can't recognize the system!");
        #endif
        #endif
    }
    inline void read2(double &x){scanf("%lf",&x);}
    inline void read2(char *s){scanf("%s",s);}
    inline void read2(char &c){scanf(" %c",&c);}
    inline void readln2(char *s){gets(s);}
    //fwrite->write
    struct Ostream_fwrite{
        char *buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        void out(char ch){
            if (p1==pend){
                fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
            }
            *p1++=ch;
        }
        void print(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(double x,int y){
            static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
                1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
                100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
            if (x<-1e-12)out('-'),x=-x;x*=mul[y];
            ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
            ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
            if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
        }
        void println(double x,int y){print(x,y);out('\n');}
        void print(char *s){while (*s)out(*s++);}
        void println(char *s){while (*s)out(*s++);out('\n');}
        void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
    }Ostream;
    inline void print(int x){Ostream.print(x);}
    inline void println(int x){Ostream.println(x);}
    inline void print(char x){Ostream.out(x);}
    inline void println(char x){Ostream.out(x);Ostream.out('\n');}
    inline void print(ll x){Ostream.print(x);}
    inline void println(ll x){Ostream.println(x);}
    inline void print(double x,int y){Ostream.print(x,y);}
    inline void println(double x,int y){Ostream.println(x,y);}
    inline void print(char *s){Ostream.print(s);}
    inline void println(char *s){Ostream.println(s);}
    inline void println(){Ostream.out('\n');}
    inline void flush(){Ostream.flush();}
    //puts->write
    char Out[OUT_SIZE],*o=Out;
    inline void print1(int x){
        static char buf[15];
        char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
        while(x)*p1++=x%10+'0',x/=10;
        while(p1--!=buf)*o++=*p1;
    }
    inline void println1(int x){print1(x);*o++='\n';}
    inline void print1(ll x){
        static char buf[25];
        char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
        while(x)*p1++=x%10+'0',x/=10;
        while(p1--!=buf)*o++=*p1;
    }
    inline void println1(ll x){print1(x);*o++='\n';}
    inline void print1(char c){*o++=c;}
    inline void println1(char c){*o++=c;*o++='\n';}
    inline void print1(char *s){while (*s)*o++=*s++;}
    inline void println1(char *s){print1(s);*o++='\n';}
    inline void println1(){*o++='\n';}
    inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}}
    struct puts_write{
        ~puts_write(){flush1();}
    }_puts;
    inline void print2(int x){printf("%d",x);}
    inline void println2(int x){printf("%d\n",x);}
    inline void print2(char x){printf("%c",x);}
    inline void println2(char x){printf("%c\n",x);}
    inline void print2(ll x){
        #ifdef _WIN32
            printf("%I64d",x);
        #else
        #ifdef __linux
            printf("%lld",x);
        #else
            puts("error:can't recognize the system!");
        #endif
        #endif
    }
    inline void println2(ll x){print2(x);printf("\n");}
    inline void println2(){printf("\n");}
    #undef ll
    #undef OUT_SIZE
    #undef BUF_SIZE
};

inline void Add_Edge(int u, int v, int w) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}	

void DFS(int w, int f) {
	fa[w][0] = f; 
	in[w] = ++div_cnt;
	dep[w] = dep[f] + 1; 
	for (register int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			dis[to[i]] = dis[w] + cost[i];
			sur[to[i]] = cost[i];
			DFS(to[i], w);
		} 
	}
	out[w] = div_cnt;
}

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

inline bool judge(int lim) {
	memset(delta,0,sizeof(delta));
	int cnt = 0, MN = 0, MX = 0;
	for (register int i=1;i<=m;i++) {
		if (q[i].len > lim) {
			cnt++;
			MN = max(MN, q[i].len - lim);
			delta[q[i].lca] -= 2;
			delta[q[i].u] ++;
			delta[q[i].v] ++;
		}
	}
	for (register int i=n;i;i--) 
		delta[i] += delta[i+1];
	
	for (register int i=1;i<=n;i++) {
		if (delta[in[i]] - delta[out[i]+1] >= cnt) {
			MX = max(sur[i], MX);
		}
	}
	return MX >= MN;
}

int main(){
	using namespace fastIO;
	int l=0,r=0,mid,ret;
	read(n); read(m);
	for (int i=1,u,v,w;i<n;i++) {
		read(u); read(v); read(w);
		l = max(l, w);
		Add_Edge(u, v, w);
	}
	DFS(1,1);
	for (int j=1;j<=19;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
		}
	}
	for (int i=1,u,v,lca;i<=m;i++) {
		read(u); read(v); lca = LCA(u, v);
		q[i].len = dis[u] + dis[v] - (dis[lca] << 1);
		r = max(r, q[i].len);
		q[i].u = in[u]; q[i].v= in[v]; q[i].lca = in[lca];
	}
	
	l = r - l; ret = r;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(mid)) ret = mid, r = mid - 1;
		else l = mid + 1; 
	}
	printf("%d\n",ret);
	return 0;
}

—– UPD 2016.11.11 —–
找高一神犇学习了一下fread的使用技巧,现在最大的一个点只用500ms辣!

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 300000+9;
const int M = N << 1;
 
int head[N],to[M],nxt[M],cost[M],sur[M],delta[N];
int dep[N],fa[N][20],in[N],out[N],dis[N],n,m,div_cnt;
struct Query{int u,v,lca,len;}q[N];

inline char Read(){
	static const int BUF_SIZE = 1000000; 
	static char buf[BUF_SIZE],*p1=0,*p2=0;
    if (p1 == p2){
    	p1=buf; p2=buf+fread(buf,1,BUF_SIZE,stdin);
		if (p2==p1) return -1;
    } return *p1++;
} 

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

inline void Add_Edge(int u, int v, int w) {
    static int T = 0;
    to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
    to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}   
 
void DFS(int w, int f) {
    fa[w][0] = f; 
    in[w] = ++div_cnt;
    dep[w] = dep[f] + 1; 
    for (register int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            dis[to[i]] = dis[w] + cost[i];
            sur[to[i]] = cost[i];
            DFS(to[i], w);
        } 
    }
    out[w] = div_cnt;
}
 
inline int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (register int j=19;~j;j--) {
        if (dep[fa[u][j]] >= dep[v]) {
            u = fa[u][j];
        }
    }
    if (u == v) return v;
    for (register int j=19;~j;j--) {
        if (fa[u][j] != fa[v][j]) {
            u = fa[u][j];
            v = fa[v][j];
        }
    }
    return fa[u][0];
}
 
inline bool judge(int lim) {
    memset(delta,0,sizeof(delta));
    int cnt = 0, MN = 0, MX = 0;
    for (register int i=1;i<=m;i++) {
        if (q[i].len > lim) {
            cnt++;
            MN = max(MN, q[i].len - lim);
            delta[q[i].lca] -= 2;
            delta[q[i].u] ++;
            delta[q[i].v] ++;
        }
    }
    for (register int i=n;i;i--) 
        delta[i] += delta[i+1];
     
    for (register int i=1;i<=n;i++) {
        if (delta[in[i]] - delta[out[i]+1] >= cnt) {
            MX = max(sur[i], MX);
        }
    }
    return MX >= MN;
}
 
int main(){
    int l=0,r=0,mid,ret;
    n = read(); m = read();
    for (int i=1,u,v,w;i<n;i++) {
        u = read(); v = read(); w = read();
        l = max(l, w);
        Add_Edge(u, v, w);
    }
    DFS(1,1);
    for (int j=1;j<=19;j++) {
        for (int i=1;i<=n;i++) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    }
    for (int i=1,u,v,lca;i<=m;i++) {
        u = read(); v = read(); lca = LCA(u, v);
        q[i].len = dis[u] + dis[v] - (dis[lca] << 1);
        r = max(r, q[i].len);
        q[i].u = in[u]; q[i].v= in[v]; q[i].lca = in[lca];
    }
     
    l = r - l; ret = r;
    while (l <= r) {
        mid = l + r >> 1;
        if (judge(mid)) ret = mid, r = mid - 1;
        else l = mid + 1; 
    }
    printf("%d\n",ret);
    return 0;
}

【Codeforces 708C】Centroids

题目传送门:http://codeforces.com/problemset/problem/708/C

我是函数式线段树+出栈入栈序的做法(其实一个RMQ即可)
但这题可以O(n)DP!记录子树中,最大的,不超过n/2的值是多少

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 800000+9;
const int M = 20000000;
const int INF = 1000000000;

int n,tot[N],ls[N],sig,rs[N],head[N],to[N],nxt[N],vex[N*2];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	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;
}

namespace Chair_Tree{
	#define CT Chair_Tree
	int sum[M][2],ch[M][2],cnt,root[N],ans_tmp;
	
	void Add(int p, int &w, int l, int r, int pos, int ty) {
		w = ++cnt; ch[w][0] = ch[p][0]; ch[w][1] = ch[p][1]; 
		sum[w][0] = sum[p][0]; sum[w][1] = sum[p][1]; sum[w][ty]++;
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (pos < mid) Add(ch[p][0],ch[w][0],l,mid-1,pos,ty);
			else Add(ch[p][1],ch[w][1],mid,r,pos,ty);
		}
	} 
	
	inline void modify(int i, int val) {
		if (val > 0) Add(root[i-1],root[i],1,n,val,1);
		else Add(root[i-1],root[i],1,n,-val,0);
	}
	
	void query(int w, int l, int r, int L, int R, int f, int ty){
		if (L <= l && r <= R) ans_tmp += sum[w][ty]*f;
		else {
			int mid = l + r + 1 >> 1;
			if (L < mid) query(ch[w][0],l,mid-1,L,R,f,ty);
			if (R >= mid) query(ch[w][1],mid,r,L,R,f,ty);
		}
	}
	
	inline int query(int l, int r, int L, int R,int ty) {
		if (l > r) return false;
		ans_tmp = 0;
		query(root[l-1],1,n,L,R,-1,ty);
		query(root[r],1,n,L,R,1,ty);
		return ans_tmp;
	}
	
	inline void Merge(){
		for (int i=1;i<=cnt;i++) 
			sum[i][0] = sum[i][1] - sum[i][0];
	}
};

void DFS(int w, int f) {
	tot[w] = 1; ls[w] = ++sig; 
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f)
		DFS(to[i],w), tot[w] += tot[to[i]];
	rs[w] = ++sig; 
	vex[ls[w]] = tot[w];
	vex[rs[w]] = -tot[w];
}

inline void AddEdge(int a, int b) {
	static int T = 0;
	to[++T] = b; nxt[T] = head[a]; head[a] = T;
	to[++T] = a; nxt[T] = head[b]; head[b] = T;
}

inline bool judge(int w) {
	int MX = 0, vx = 0, MN, ty, sta;
	for (int i=head[w];i;i=nxt[i]) 
		if (ls[w] < ls[to[i]] && ls[to[i]] <= rs[w]) {if (MX < tot[to[i]]) MX = tot[to[i]], vx = to[i], ty = 0;} 
		else {int tmp = n - tot[w]; if (MX < tmp) MX = tmp, vx = to[i], ty = 1;}
	if (MX <= n/2) return 1;
	else {
		sta = n/2;
		MN = MX-n/2;
		if (!ty) return CT::query(ls[vx],rs[vx],MN,sta,1);
		else {
			int tmp = CT::query(1,ls[w]-1,MN,sta,1) + CT::query(rs[w]+1,n*2,MN,sta,1);
			tmp -= CT::query(1,ls[w]-1,MN,sta,0); MN = n - MN; sta = n - sta; swap(MN,sta);
			tmp += CT::query(2,ls[w],MN,sta,0);
			return tmp;
		}
	}
}

int main(){
	n = read(); 
	for (int i=1;i<n;i++) AddEdge(read(),read()); DFS(1,1);
	for (int i=1;i<=n*2;i++) CT::modify(i,vex[i]); CT::Merge();
	for (int i=1;i<=n;i++) printf("%d ",judge(i));
	return 0;
}