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

【日常小测】最长公共前缀

题目大意

给定一棵以$1$号点为根、大小为$n$的有根树($n \le 10^5$),每一条边上有一个小写英文字母
给定$m$个询问,第$i$个询问包含一个长度为$t_i$的点集(元素可重,$\sum{t_i} \le 2 \cdot 10^5$),询问$\sum\limits_{a=1}^{t_i}{\sum\limits_{b=a+1}^{t_i}{lcp(a,b)}}$

定义$s_a$为从a出发走向根,将边上的字符按顺序写下来构成的字符串
定义$lcp(a,b)$为$s_a$与$s_b$的最长公共前缀

下面举一个栗子
若树长成这样:

那么$s_5=cb,s_4=cbb$
更进一步,若某次询问的点集为$\{4,5\}$那么答案为$2$

解题报告

看到这种树上的字符串,我能想到AC自动机,或者广义后缀自动机
想了想AC自动机做不了,那就广义后缀自动机来做咯!

考虑后缀自动机上的Fail树
一个点的祖先实际上是这个点代表的字符串的后缀
那么题目中的$lcp(a,b)$就变成了$lca(a,b)$
于是对于每一次询问,我们建一个虚树出来
然后在虚树上DFS一次,统计一下答案就好啦!

另外,这题用后缀数组也可以做!
听武爷讲一讲,大概就是先把Trie树建出来
同时记录下每一次倍增的$Rank$数组(波兰表……)
然后就正常倍增,写法已经和罗穗骞的后缀数组的实现很不同了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 200009;
const int M = N << 1;
 
int n,m,E,head[N],nxt[M],to[M],col[M],pos[N],id[N];
 
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, int c = 0) {
    to[++E] = v; nxt[E] = head[u]; head[u] = E; col[E] = c;
    to[++E] = u; nxt[E] = head[v]; head[v] = E; col[E] = c;
}   
 
class Suffix_Automaton{
	int cnt=1,ch[N][26],fail[N],vis[N],dep[N],sum[N];
	int tot,arr[N],que[N],len[N],fa[N][20],_hash[N];
	vector<int> G[N]; LL ans_tmp;
    public:
        inline int insert(int t, int cc) {
            if (ch[t][cc] && len[ch[t][cc]] == len[t] + 1) return ch[t][cc];
            int tail = ++cnt; len[tail] = len[t] + 1;
            while (!ch[t][cc] && t) ch[t][cc] = tail, t=fail[t];
            if (!t) fail[tail] = 1;
            else {
                if (len[ch[t][cc]] == len[t] + 1) fail[tail] = ch[t][cc];
                else {
                    int nw = ++cnt, w = ch[t][cc]; len[nw] = len[t]+1;
                    memcpy(ch[nw], ch[w], sizeof(ch[nw]));
                    fail[nw] = fail[w]; fail[w] = fail[tail] = nw;
                    for (;ch[t][cc]==w;t=fail[t]) ch[t][cc] = nw;
                }
            } return tail;
        }
        inline void Build_Fail_Tree() {
            memset(head,0,sizeof(head)); E = 0;
            for (int i=2;i<=cnt;i++) Add_Edge(fail[i], i);
            dfs(1, 1);
            for (int j=1;j<20;j++) {
                for (int i=1;i<=cnt;i++) {
                    fa[i][j] = fa[fa[i][j-1]][j-1];
                }
            }   
        }
        inline LL solve(int nn) {
            for (int i=1;i<=nn;i++) arr[i] = pos[read()];
            sort(arr+1, arr+1+nn, [](const int &a, const int &b) {return id[a] < id[b];});
            for (int i=1;i<=nn;i++) _hash[i] = arr[i];
            int mm = nn; nn = unique(arr+1, arr+1+nn) - arr - 1;
            for (int i=1;i<=nn;i++) sum[i] = 0;
            for (int i=1,j=1;i<=mm;i++) {
                while (arr[j] != _hash[i]) j++;
                sum[j]++;
            }
            que[tot=1] = 1; int MX = 1;
            for (int i=1,lca;i<=nn;i++) {
                vis[arr[i]] = sum[i];
                lca = LCA(que[tot], arr[i]);
                while (dep[que[tot]] > dep[lca]) {
                    if (dep[que[tot-1]] >= dep[lca]) G[que[tot-1]].push_back(que[tot]);
                    else G[lca].push_back(que[tot]);
                    --tot;
                }
                if (que[tot] != lca) que[++tot] = lca;
                if (arr[i] != que[tot]) que[++tot] = arr[i];
                MX = max(MX, tot);
            }
            while (tot > 1) G[que[tot-1]].push_back(que[tot]), --tot;
            ans_tmp = 0;
            Get_Ans(1);
            return ans_tmp;
        }
    private:
        void dfs(int w, int f) {
            static int id_count = 0;
            id[w] = ++id_count;
            fa[w][0] = f; dep[w] = dep[f] + 1;
            for (int i=head[w];i;i=nxt[i]) {
                if (to[i] != f) {
                    dfs(to[i], w);
                }
            }
        } 
        int Get_Ans(int w) {
            int ret = vis[w]; 
            if (w > 1) ans_tmp += vis[w] * (vis[w] - 1ll) / 2 * len[w]; 
            for (int i=G[w].size()-1,tmp;~i;i--) { 
                tmp = Get_Ans(G[w][i]);
                ans_tmp += (LL)tmp * ret * len[w];
                ret += tmp;
            }
            vis[w] = 0; 
            G[w].clear();
            return ret;
        }
        inline int LCA(int a, int b) {
            if (dep[a] < dep[b]) swap(a, b);
            for (int i=19;~i;i--) if (dep[fa[a][i]] >= dep[b]) a = fa[a][i];
            if (a == b) return a;
            for (int i=19;~i;i--) if (fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
            return fa[a][0];
        }   
}SAM;
 
void DFS(int w, int f, int t) {
    pos[w] = t;
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            int nt = SAM.insert(t, col[i]);
            DFS(to[i], w, nt);
        }
    }
}
 
int main() {
    n = read(); char pat[10];
    for (int i=1,u,v;i<n;i++) {
        u = read(); v = read();
        scanf("%s",pat+1);
        Add_Edge(u, v, pat[1] - 'a');
    }   
    DFS(1, 1, 1);
    SAM.Build_Fail_Tree();
    for (int i=read();i;i--) 
        printf("%lld\n",SAM.solve(read()));
    return 0;
}

【CodeChef BTREE】Union on Tree

相关链接

题目传送门:https://www.codechef.com/problems/BTREE
数据生成器:http://paste.ubuntu.com/23671176/
中文题面:http://www.codechef.com/download/translated/OCT14/mandarin/BTREE.pdf
官方题解:https://discuss.codechef.com/questions/53273/btree-editorial
神犇题解Ⅰ:http://xllend3.is-programmer.com/posts/64760.html
神犇题解Ⅱ:https://stalker-blog.apphb.com/post/divide-and-conquer-on-trees-based-on-vertexes

WJMZBMR Orz

又是 青年计算机科学家陈立杰 出的神题!
真的是跪烂!_(:з」∠)_

解题报告

看一看数据范围就可以知道这题复杂度一定只跟 ∑士兵数 相关
于是考虑先把虚树建出来,那么剩下的问题就是在利用虚树的边来统计答案了

1)函数式线段树的做法

考虑k=1,这样的话不用处理重复的问题,于是直接点分治就可以做
但现在有很多的点,于是我们可以将树剖成很多块,每块中恰好又一个城市a有卫兵
更进一步,我们规定这个联通块中任意一个点i到a的距离不大于到其他任意有卫兵的城市的距离
于是我们如果能在每一个联通块中单独处理每一个卫兵的话,就可以不用考虑去重的问题了

我们再仔细观察一下建出来的虚树,发现每一个块就是虚树上的一部分
对于a所在联通块深度最小的那个点,统计一下、加到答案里去
对于a所在联通块的其余边缘节点,再统计一下、从答案中减去

于是剩下的就是如何具体如何统计一条边对于答案的贡献了
我们分两种情况考虑:

  1. v不是u在虚树中的祖先,统计v的子树中、到u的距离为d的点的个数
    这个的话,直接用函数式线段树查就好
  2. v是u的父亲,其余条件相同
    这样的话,似乎与v的距离就不固定了(lca在u ~ v中移动)
    于是先用点分治做出所有点到u的距离为d的点的个数n1
    然后需要减掉v子树外的部分,这样的话,发现到v的距离就固定了
    于是减掉所有点到v的距离为d-dis(u,v)的点数n2
    再加上v子树中到v距离为d-dis(u,v)的点数n3就可以辣!

2)直接用点分治的做法

先用把点分树搞出来,这样就可以O(log^2(n))的时间复杂度内求dis(w,d)
其中dis(w,d)的定义为 到点w距离在d以内的点有多少 (不会的同学可以先去做BZOJ_3730

再考虑把虚树建出来,这样的话唯一的问题就是如何去重了
考虑如果虚树上一条边的两个点的管辖范围没有交集,那么就肯定没有重复
如果有交集,那么设交集的重点为m,交集半径为r'那么直接减掉dis(m,r')就可以辣!

另外还需要预先将完全包含的管辖区间给修改成“相切”的情况,这样才能保证去重完整
还有的话,中点可能落在边上,于是可以在每边的中点加一个点

这样的做法是不是比主席树的做法清真了很多?
然而我还是写了5k+ _ (:з」∠) _
而且如果边带权的话,这题就很难这样做了

Code

最近为什么写啥常数都大到不行啊 QwQ
又是垫底…..

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

const int N = 100000 + 9;
const int M = N << 1;
const int INF = 1e8;

int n,m,T,head[N],to[M],nxt[M],num[N],cost[N];
int anc[N][18],dep[N],val[N],p[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) {
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

void DFS(int w, int f) {
	static int cnt = 0;
	dep[w] = dep[f] + 1;
	anc[w][0] = f; num[w] = ++cnt;
	for (int i=head[w];i;i=nxt[i]) {
		if (!dep[to[i]]) {
			DFS(to[i], w);
		}
	}
}

inline int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=17;~i;i--) 
		if (dep[anc[x][i]] >= dep[y]) 
			x = anc[x][i];
	if (x == y) return x;
	for (int i=17;~i;i--) {
		if (anc[x][i] != anc[y][i]) {
			x = anc[x][i];
			y = anc[y][i];
		}
	} 
	return anc[x][0];
}

inline int dis(int x, int y) {
	int lca = LCA(x, y);
	return dep[x] + dep[y] - dep[lca] * 2;
}

class Point_Based_Divide_and_Conquer{
	int fa[N][18],tot[N],sum[N];
	int ans_tmp,root,block_size;
	vector<int> q[N],mul[N];
	bool vis[N];
	
	public: 	
		inline void init() {
			block_size = n;
			ans_tmp = INF;
			Get_Root(1, 1);
			tot[root] = 1;
			build(root, n);	
		}
		
		inline int query(int w, int rag) {
			int ret = Query(w, rag, q);
			for (int i=1,t;i<tot[w];i++) {
				t = rag - dis(fa[w][i], w);
				if (t >= 0) {
					ret += Query(fa[w][i], t, q);
					ret -= Query(fa[w][i-1], t, mul);
				}
			}
			return ret;
		}
	private:
		void Get_Root(int w, int f) {
			int mx = 0; sum[w] = 1;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && !vis[to[i]]) {
					Get_Root(to[i], w);
					mx = max(mx, sum[to[i]]);
					sum[w] += sum[to[i]];
				}
			}
			mx = max(block_size - sum[w], mx);
			if (mx < ans_tmp) {
				ans_tmp = mx;
				root = w;
			}
		}
		
		void build(int w, int sz) {
			vis[w] = 1; fa[w][0] = w;
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]]) {
					block_size = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
					ans_tmp = INF; Get_Root(to[i], w);
					memcpy(fa[root]+1, fa[w], sizeof(fa[w])-sizeof(int));
					tot[root] = tot[w] + 1;
					build(root, block_size);
				}
			}
			
			if (val[w]) {
				for (int i=0;i<tot[w];i++) 
					q[fa[w][i]].push_back(dis(w, fa[w][i]));
				for (int i=0;i<tot[w]-1;i++)
					mul[fa[w][i]].push_back(dis(w, fa[w][i+1]));	
			}
			sort(q[w].begin(), q[w].end());
			sort(mul[w].begin(), mul[w].end());
		} 
		
		inline int Query(int w, int r, vector<int> *a) {
			return upper_bound(a[w].begin(), a[w].end(), r) - a[w].begin();
		}
}PDC; 

class Virtual_Tree{
	int stk[N],rag[N],top,lca,cnt,root;
	queue<int> que;
	bool inq[N];
	
	public:	
		inline void build(int &tot) {
			cnt = tot; T = 0;
			root = p[1] = read(); 
			newnode(p[1], read());
			for (int i=2;i<=tot;i++) {
				p[i] = read();
				newnode(p[i], read());
				root = LCA(root, p[i]);
			}
			static auto cmp = [](int a, int b) {return num[a] < num[b];};
			sort(p+1, p+1+tot, cmp);
			if (root != p[1]) p[++tot] = root, newnode(root, -1);
			stk[top=1] = root;
			for (int i=1+(p[1]==root);i<=cnt;i++) {
				lca = LCA(p[i], stk[top]);
				for (;dep[stk[top]] > dep[lca];top--) 
					if (dep[stk[top-1]] >= dep[lca]) AddEdge(stk[top-1], stk[top]);
					else newnode(lca, -1), AddEdge(lca, stk[top]);
				if (lca != stk[top]) 
					stk[++top] = p[++tot] = lca;
				if (p[i] != stk[top])
					stk[++top] = p[i];
			}
			for (int i=1;i<top;i++)
				AddEdge(stk[i], stk[i+1]);
		}
		
		inline int solve(int tot) {
			prework(tot);
			int ret = 0;
			for (int i=1,u,v,r,mid,t;i<T;i+=2) {
				u = to[i]; v = to[i+1];
				r = rag[u] + rag[v] - cost[i] >> 1;
				if (r >= 0) {
					mid = move(u, v, r);
					ret -= PDC.query(mid, r);
				}
			} 
			for (int i=1;i<=tot;i++) 
				ret += PDC.query(p[i], rag[p[i]]);
			return ret;
		}
	private:
		inline void newnode(int w, int v) {
			rag[w] = v << 1;
			head[w] = 0;
		}
		
		inline int move(int x, int y, int r) {
			if (dep[x] < dep[y]) swap(x, y);
			r = rag[x] - r;
			for (int i=0;r;i++,r>>=1)
				if (r & 1) x = anc[x][i];
			return x;	 
		}
		
		inline void prework(int tot) {
			for (int i=1;i<=tot;i++) {
				que.push(p[i]);
				inq[p[i]] = 1;
			}
			
			while (!que.empty()) {
				int w = que.front(); 
				que.pop(); inq[w] = 0;
				for (int i=head[w];i;i=nxt[i]) {
					if (rag[w] > rag[to[i]] + cost[i]) {
						rag[to[i]] = rag[w] - cost[i];
						if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
					}
				}
			}
		}
		
		inline void AddEdge(int u, int v) {
			int w = dis(u, v);
			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;
		}
}VT; 

int main() {
	n = read();
	fill(val+1, val+1+n, 1);
	for (int i=1,lim=n,u,v;i<lim;i++) {
		u = read(); v = read();
		Add_Edge(u, ++n);
		Add_Edge(n, v);
	}
	
	DFS(1, 1);
	for (int j=1;j<=17;j++) {
		for (int i=1;i<=n;i++) {
			anc[i][j] = anc[anc[i][j-1]][j-1];
		}
	}
	PDC.init();
	
	m = read();
	for (int y=1,k;y<=m;y++) {
		VT.build(k = read());
		printf("%d\n",VT.solve(k)); 
	}
	return 0;
}

【BZOJ 3572】[Hnoi2014] 世界树

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3572
数据生成器:http://paste.ubuntu.com/23376760/

一看数据范围肯定知道是虚树辣!
题解的话,让我们召唤曹清华:http://blog.csdn.net/jzhang1/article/details/50630194
然后就是恶心的码代码环节…..
人太懒,于是带了两个log,慢成翔 qwq

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)<0?-(x):(x))
using namespace std;

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

int head[N],nxt[M],to[M],T,n,m,tot,num[N],blg[N],p[N],sz[N];
int stk[N],top,dep[N],fa[N][18],size[N],vis[N],vout[N];

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 AddEdge(int u, int v) {to[++T] = v; nxt[T] = head[u]; head[u] = T;}
inline void Add_Edge(int u, int v) {AddEdge(u,v);AddEdge(v,u);}
inline bool CMP(int a, int b) {return num[a] < num[b];}

void DFS(int w, int f) {
	static int dfs_cnt = 0; num[w] = ++dfs_cnt;
	fa[w][0] = f; dep[w] = dep[f]+1; size[w] = 1;
	for (int i=1;i<=17;i++) fa[w][i] = fa[fa[w][i-1]][i-1];
	
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
			size[w] += size[to[i]];
		}
	}
}

inline int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=17;~i;i--) {
		if (dep[fa[x][i]] >= dep[y]) {
			x = fa[x][i];
		}
	}
	if (x == y) return x;
	for (int i=17;~i;i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}

inline int dis(int x, int y) {
	int lca = LCA(x, y);
	return dep[x] + dep[y] - dep[lca]*2;
}

inline void Build(int root) {
	p[++tot] = root; 
	stk[top=1] = root;
	sz[root] = n;
	
	for (int i=1,w,lca;i<=m;i++) {
		w = p[i]; lca = LCA(stk[top],w);
		while (dep[stk[top]] > dep[lca]) {
			if (dep[stk[top-1]] < dep[lca]) 
				AddEdge(lca, stk[top]);
			else 
				AddEdge(stk[top-1], stk[top]);
			top--;
		}
		if (lca != stk[top]) {
			stk[++top] = lca;
			p[++tot] = lca;
			sz[lca] = size[lca] - 1;
		} 
		if (w != stk[top]) {
			stk[++top] = w;
			sz[w] = size[w] - 1;
		}
	}
	for (int i=1;i<top;i++) 
		AddEdge(stk[i], stk[i+1]);
}

void prework_1(int w, int up) {
	blg[w] = vis[w]?w:up; 
	for (int i=head[w];i;i=nxt[i]) {
		prework_1(to[i], vis[w]?w:up);
		if (~blg[to[i]]) {
			int len1 = (~blg[w]?abs(dep[blg[w]] - dep[w]):INF);
			int len2 = abs(dep[blg[to[i]]] - dep[w]);
			if (!~blg[w] || len1 > len2 || (len1 == len2 && blg[to[i]] < blg[w])) 
				blg[w] = blg[to[i]];
		}
	}
}

void prework_2(int w) {
	for (int i=head[w];i;i=nxt[i]) {
		if (blg[w] != blg[to[i]]) {
			int len1 = dis(blg[w], to[i]);
			int len2 = dis(blg[to[i]], to[i]);
			if (len1 < len2 || (len1 == len2 && blg[w] < blg[to[i]])) 
				blg[to[i]] = blg[w];
		}
		prework_2(to[i]);
	}
}

void solve(int w) {
	for (int i=head[w],len,cur;i;i=nxt[i]) {
		top = to[i];
		for (int j=17;~j;j--) {
			if (dep[fa[top][j]] > dep[w]) 
				top = fa[top][j];
		}
		sz[w] -= size[top];
		
		if (blg[w] == blg[to[i]]) {
			vout[vis[blg[w]]] += size[top] - size[to[i]] + 1;
		} else {
			cur = to[i];
			for (int j=17;~j;j--) {
				if (dis(fa[cur][j],blg[w]) > dis(blg[to[i]], fa[cur][j])) 
					cur = fa[cur][j];
			}
			vout[vis[blg[to[i]]]] += size[cur] - size[to[i]] + 1;
			if (dep[fa[cur][0]] > dep[w] && dis(fa[cur][0], blg[w]) == dis(fa[cur][0], blg[to[i]])){
				vout[vis[min(blg[w], blg[to[i]])]] += size[fa[cur][0]] - size[cur];
				vout[vis[blg[w]]] += size[top] - size[fa[cur][0]];
			} else {
				vout[vis[blg[w]]] += size[top] - size[cur];
			}
		}
		solve(to[i]);
	}
	vout[vis[blg[w]]] += sz[w];
}

int main(){
	n = read();
	for (int i=1;i<n;i++) 
		Add_Edge(read(),read()); 
	DFS(1,1);
	
	T = 0; memset(head,0,sizeof(head));
	for (int q=read(),lca;q;q--) {
		m = tot = read(); 
		lca = p[1] = read();
		vis[p[1]] = 1; vout[1] = 0;
		for (int i=2;i<=m;i++) {
			vis[p[i]=read()] = i;
			lca = LCA(lca, p[i]);
			vout[i] = 0;
		}
		sort(p+1, p+1+m, CMP);
		
		Build(lca);
		prework_1(lca,-1);
		prework_2(lca);
		solve(lca);
		for (int i=1;i<=m;i++) {
			printf("%d ",vout[i]);
		} putchar('\n');
		
		for (int i=1;i<=tot;i++) {
			vis[p[i]] = head[p[i]] = 0;
		} T = 0;
	}
	return 0;
}

【BZOJ 2286】[Sdoi2011] 消耗战

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2286
数据生成器:http://paste.ubuntu.com/23372796/

就是把虚树建出来了以后,在虚树上跑树上DP
DP很好想,只需要会建虚树就可以辣!

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

const int SGZ = 18;
const int M = 500000+9;
const int N = 250000+9;
const int INF = 0x7fffffff;

int head[N],nxt[M],to[M],cost[M],dep[N],fa[N][SGZ],MN[N][SGZ];
int n,m,p[N],num[N],stk[N],top,tot,T;
bool vis[N]; 

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) {
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

inline void Add_Edge(int u, int v, int w) {
	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) {
	static int dfs_cnt = 0; num[w] = ++dfs_cnt;
	fa[w][0] = f; dep[w] = dep[f] + 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
			MN[to[i]][0] = cost[i];
		}
	}
}

inline bool CMP(const int &x, const int &y) {
	return num[x] < num[y];
}

inline int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=17;~i;i--) {
		if (dep[fa[x][i]] >= dep[y]) {
			x = fa[x][i];
		}
	}
	if (x == y) return x;
	for (int i=17;~i;i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
} 

inline int Get_Cost(int w, int pur) {
	int ret = INF; pur = dep[pur];
	for (int i=17;~i;i--) {
		if (dep[fa[w][i]] >= pur) {
			ret = min(ret, MN[w][i]);
			w = fa[w][i];
		}
	}
	return ret;
}

inline void build() {
	stk[top = 1] = 1;
	for (int i=1,w,lca;i<=m;i++) {
		w = p[i]; lca = LCA(stk[top], w);
		while (dep[stk[top]] > dep[lca]) {
			if (dep[stk[top-1]] <= dep[lca]) 
				Add_Edge(lca, stk[top]);
			else 
				Add_Edge(stk[top-1], stk[top]);
			--top;
		}
		if (stk[top] != lca) stk[++top] = lca, p[++tot] = lca;
		stk[++top] = w;
	}
	for (int i=1;i<top;i++) 
		Add_Edge(stk[i], stk[i+1]);
}

inline LL DP(int w, int f) {
	LL tmp = 0;
	for (int i=head[w];i;i=nxt[i]) 
		tmp += DP(to[i], w);
	if (vis[w]) return Get_Cost(w, f);
	else if (w != 1) return min((LL)Get_Cost(w, f), tmp);
	else return tmp;
}

int main() {
	n = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		Add_Edge(u, v, read());
	}
	
	DFS(1, 1); MN[1][0] = INF;
	for (int j=1;j<=17;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
			MN[i][j] = min(MN[i][j-1], MN[fa[i][j-1]][j-1]);
		}
	} 
	
	memset(head,0,sizeof(head));
	for (int k=read();k;k--) { 
		m = tot = read(); T = 0; 
		for (int i=1;i<=m;i++) vis[p[i] = read()] = 1;
		sort(p+1, p+1+m, CMP);
		build();
		printf("%lld\n",DP(1,1)); head[1] = 0;
		for (int i=1;i<=tot;i++) vis[p[i]] = 0, head[p[i]] = 0;
	}
	return 0;
}