【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即可

【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)$

【日常小测】路径规划

题目大意

给定一棵$n(n \le 3 \cdot 10^5)$个点无根带边权的树
要求找出一条路径使得该路径上边权的最小值乘边权和最大

解题报告

这题啊!我们可以无脑点分对不对啊?
时间复杂度$O(n \log ^2 n)$,卡卡常数能过去

但这题更优雅的做法是维护直径
就像51nod上一个题一样,每一块内搞一个直径
合并两个块后生成的大块的直径一定在这四个点之间
于是就一路合并上去就可以辣!
时间复杂度:$O(n \log n)$

Code

点分治版本:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 300009;
const int M = N << 1;
const int INF = 1e9;
 
int n,head[N],nxt[M],to[M],cost[M];
LL vout;
 
inline void Add_Edge(int u, int v, int c) {
    static int E = 1; 
    to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
    to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;
}
 
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;
}
 
class Divide_and_Conquer{
    int rt,rt_sz,blk_sz,tot,sz[N],vis[N];
    struct Data{
        int mn,id; LL sum;
        inline bool operator < (const Data &B) const {
            return mn < B.mn;
        }
    }sta[N];
    public:
        void solve(int w, int blk) { 
            GetRoot(w, blk); vis[w=rt] = 1; tot = 0;
            for (int i=head[w];i;i=nxt[i]) {
                if (!vis[to[i]]) {
                    DFS(to[i], w, to[i], cost[i], cost[i]);
                }
            } 
            if (tot) update(); 
            for (int i=head[w];i;i=nxt[i]) {
                if (!vis[to[i]]) { 
                    if (sz[to[i]] > sz[w]) sz[to[i]] = blk - sz[w];
                    solve(to[i], sz[to[i]]);
                }
            }
        }
    private:
        inline void update() {
            sort(sta+1, sta+1+tot);
            LL mx1=0,mx2=0; int sur1=0,sur2=0;
            for (int i=tot;i;i--) {
                vout = max(vout, sta[i].mn * sta[i].sum);
                if (sur1 && sur1 != sta[i].id) {
                    vout = max(vout, (mx1 + sta[i].sum) * sta[i].mn);
                } else if (sur2 && sur2 != sta[i].id) {
                    vout = max(vout, (mx2 + sta[i].sum) * sta[i].mn);
                }
                if (sta[i].sum > mx1) {
                    if (sur1 == sta[i].id) {
                        mx1 = sta[i].sum;
                    } else {
                        mx2 = mx1; sur2 = sur1;
                        mx1 = sta[i].sum; sur1 = sta[i].id;
                    }
                } else if (sta[i].sum > mx2) {
                    if (sur1 != sta[i].id) {
                        sur2 = sta[i].id;
                        mx2 = sta[i].sum;
                    }
                }
            }
        }
        inline void GetRoot(int w, int blk) {
            rt_sz = INF; blk_sz = blk;
            GetRoot1(w, w); 
        }
        void GetRoot1(int w, int f) {
            sz[w] = 1; int mx = 1;
            for (int i=head[w];i;i=nxt[i]) {
                if (to[i] != f && !vis[to[i]]) {
                    GetRoot1(to[i], w);
                    sz[w] += sz[to[i]];
                    mx = max(mx, sz[to[i]]);
                }
            }
            mx = max(mx, blk_sz - sz[w]);
            if (mx < rt_sz) rt_sz = mx, rt = w;
        }
        void DFS(int w, int f, int top, int mn, LL sum) {
        	bool tag = 1;
            for (int i=head[w];i;i=nxt[i]) {
                if (to[i] != f && !vis[to[i]]) {
                    DFS(to[i], w, top, mn>cost[i]?cost[i]:(tag=0,mn), cost[i] + sum);
				}
            }
            if (!tag) return;
            sta[++tot].mn = mn; sta[tot].id = top; sta[tot].sum = sum;
        }
}DAC;
 
int main() {
    n = read();
    for (int i=1,u,v;i<n;i++) {
        u = read(); v = read();
        Add_Edge(u, v, read());
    }
    DAC.solve(1, n);
    printf("%lld\n",vout);
    return 0;
}

维护直径版本:

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

const int N = 300009; 
const int M = N << 1;

int n,head[N],nxt[M],to[M],cost[M];
int stp[N],p[N][2],fa[N][20],anc[N];
struct Edge{int u,v,c;}e[N];
LL vout,dep[N],MX[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;
}

void DFS(int w, int f) {
	fa[w][0] = f; stp[w] = stp[f] + 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			dep[to[i]] = dep[w] + cost[i];
			DFS(to[i], w);
		}
	}
}

inline void AddEdge(int u, int v, int c, int id) {
	static int E = 1; cost[E+1] = cost[E+2] = c;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
	e[id] = (Edge){u, v, c};
}

inline LL Dis(int u, int v) {
	if (stp[v] < stp[u]) swap(u, v); int p1 = u, p2 = v;
	for (int i=19;~i;i--) if (stp[fa[v][i]]>=stp[u]) v = fa[v][i];
	if (u == v) return dep[p2] - dep[u];
	for (int i=19;~i;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
	return -(dep[fa[u][0]]<<1) + dep[p1] + dep[p2];
}

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

inline LL Merge(int u, int v) {
	static LL ret, p1, p2; u = find(u); v = find(v);
	if (MX[u] > MX[v]) ret = MX[u], p1 = p[u][0], p2 = p[u][1];
	else ret = MX[v], p1 = p[v][0], p2 = p[v][1]; 
	for (int i=0;i<=1;i++) {
		for (int j=0;j<=1;j++) {
			LL cur = Dis(p[u][i], p[v][j]);
			if (cur > ret) {
				ret = cur; 
				p1 = p[u][i];
				p2 = p[v][j];
			}
		}
	}
	anc[u] = v; MX[v] = ret;
	p[v][0] = p1; p[v][1] = p2;
	return ret;
}

int main() {
	n = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		AddEdge(u, v, read(), i);
	} 
	DFS(1, 1);
	for (int j=1;j<20;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
		}
	}
	sort(e+1, e+N, [](const Edge &A, const Edge &B){return A.c > B.c;});
	for (int i=1;i<=n;i++) {
		anc[i] = i;
		p[i][0] = p[i][1] = i;
	}	
	for (int i=1;i<n;i++) {
		LL tmp = Merge(e[i].u, e[i].v);
		vout = max(vout, tmp * e[i].c);
	}
	printf("%lld\n",vout);
	return 0;
}

【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

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

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

【CodeChef PRIMEDST】Prime Distance On Tree

相关链接

题目传送门:https://www.codechef.com/problems/PRIMEDST
官方题解:https://www.codechef.com/problems/PRIMEDST
神犇题解:https://stalker-blog.apphb.com/post/divide-and-conquer-on-trees-based-on-vertexes

解题报告

考虑使用点分治来统计答案,实际是求
\(\sum\limits_{i + j = prime\_number} {nu{m_i} \cdot nu{m_j}}\)
然后发现这货是个卷积的形式,于是点分的时候搞一搞FFT就可以啦!

值得注意的是,在FFT的时候答案可能会爆int
不要问我是怎么知道的

Code

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

const int N = 66000;
const int M = 110000;
const int INF = 1e9;
const double EPS = 1e-2;
const double PI = acos(-1);

int n,head[N],to[M],nxt[M];
LL vout;

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

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 Fast_Fourier_Transform{
	typedef complex<double> E;
	complex<double> a[N<<1];
	int pri[M],vis[M],pos[N<<1],tot,len,stp;
	public:
		Fast_Fourier_Transform() {
			for (int i=2;i<M;i++) {
				if (!vis[i]) pri[++tot] = i;
				for (int j=1;j<=tot&&pri[j]*i<M;j++) {
					vis[i*pri[j]] = 1;
					if (i%pri[j] == 0) break;
				}	
			}
		}
		inline LL solve(int t, int *arr) {
			for (len=1,stp=-1;len<=t*2;len<<=1,++stp);
			memset(a,0,sizeof(E)*(len+9));
			for (int i=0;i<=t;i++) 
				a[i].real() = arr[i];
			for (int i=1;i<len;i++) { 
				pos[i] = pos[i>>1] >> 1;
				if (i & 1) pos[i] |= 1 << stp;
			} 
			
			fft(a, 1);
 			for (int i=0;i<len;i++)
				a[i] *= a[i];
			fft(a, -1);
			LL ret = 0;
			for (int i=1;i<=tot&&pri[i]<=t*2;i++)
				ret += a[pri[i]].real() / len + EPS;
			return ret;
		}
	private:
		inline void fft(E *arr, int t) {
			for (int i=0;i<len;i++)
				if (pos[i] < i) swap(arr[pos[i]], arr[i]);
			for (int k=0,gap=2;k<=stp;k++,gap<<=1) {
				E wn(cos(2*PI/gap),t*sin(2*PI/gap));
				for (int j=0;j<len;j+=gap) {
					complex<double> cur(1, 0),t1,t2;
					for (int i=j;i<j+gap/2;i++,cur*=wn) {
						t1 = arr[i]; t2 = cur * arr[i+gap/2];
						arr[i] = t1 + t2;
						arr[i+gap/2] = t1 - t2;
					}
				}
			}
		}
}FFT;

class Node_Based_Divide_and_Conquer{
	int area_size,cur_ans,root,tot;
	int sum[N],vis[N],cnt[N];
	public:
		inline void solve() {
			area_size = n; cur_ans = INF;
			Get_Root(1, 1);
			work(root, area_size);
		}
	private:
		void work(int w, int sz) {
			vis[w] = 1; 
			vout += solve(w, 0);
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]]) {
					vout -= solve(to[i], 1);
					area_size = sum[to[i]]<sum[w]? sum[to[i]]: sz - sum[w];
					cur_ans = INF; Get_Root(to[i], w);
					work(root, area_size);
				}
			}
		}
		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);
					sum[w] += sum[to[i]];
					mx = max(mx, sum[to[i]]);
				}
			}
			mx = max(mx, area_size - sum[w]);
			if (mx < cur_ans) {
				cur_ans = mx;
				root = w;
			}	
		}
		LL solve(int w, int bas) {
			memset(cnt,0,sizeof(int)*(tot+9));
			tot = 0; Get_Dis(w, bas, w);
			return FFT.solve(tot, cnt);
		} 
		void Get_Dis(int w, int d, int f) {
			cnt[d]++; 
			tot = max(tot, d);
			for (int i=head[w];i;i=nxt[i]) 
				if (to[i] != f && !vis[to[i]]) 
					Get_Dis(to[i], d+1, w);
		}
}NDC;

int main() {
	n = read();
	for (int i=1;i<n;i++) 
		Add_Edge(read(), read());
	NDC.solve();
	printf("%.10lf\n",(double)vout/n/(n-1));
	return 0;
}

【Codeforces 100633D】LWDB

相关链接

题目传送门:http://codeforces.com/problemset/gymProblem/100633/D
中文题面:http://paste.ubuntu.com/23661606/

解题报告

直接考虑将其用点分树搞
对于每一个合法的染色,我们尝试在第一个将染色点a被染色点b分开的分治点c处进行更新
因为是第一个分开的分治点,所以a、b一定在c的不同子树中
不妨设a的染色范围为d,那么对于任意点b来讲,距离c的距离 <= d-dis(a,c)就好

于是修改操作就暴力爬树高,维护一个单调栈
查询操作也是暴力爬树高,在每一个单调栈那里二分出最后生效的染色点即可

Code

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

const int N = 100000+9;
const int M = N << 1;
const int L = 20;
const int INF = 1e9;

int head[N],to[M],nxt[M],cost[M],dis[N],dep[N];
int n,m,fa[N][L];

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, 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;
	dep[w] = dep[f] + 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			dis[to[i]] = dis[w] + cost[i];
			DFS(to[i], w);
		}
	}
}

inline int DIS(int x, int y) {
	int ret = dis[x] + dis[y];
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=L-1;~i;i--) 
		if (dep[fa[x][i]] >= dep[y]) 
			x = fa[x][i];
	if (x == y) return ret - dis[x] * 2;
	for (int i=L-1;~i;i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return ret - dis[fa[x][0]] * 2;
}

class Node_Based_Divide_and_Conquer{
	int cur_ans,root,area_size,rod[N][L];
	int sum[N],vis[N],anc[N][L],len[N];
	struct Data{
		int x,y,z;
		inline bool operator < (const Data &B) const {return x < B.x;}
		inline bool operator <= (const Data &B) const {return x <= B.x;}
	}tmp;
	vector<Data> stk[N];
	vector<Data>::reverse_iterator itr;
	public:
		inline void init() {
			area_size = n; cur_ans = INF;
			Get_Root(1, 1); len[root] = 1;
			Build(root, n);
		}
		inline void modify(int w, int d, int c, int id) {
			tmp.y = c; tmp.z = id;
			for (int i=0,p;i<len[w];i++) {
				p = anc[w][i]; tmp.x = d - rod[w][i];
				if (tmp.x >= 0) {
					while (!stk[p].empty() && stk[p].back() <= tmp) stk[p].pop_back();
					stk[p].push_back(tmp);
				}
			}
		}
		inline int query(int w) {
			Data ret={0,0,0};
			for (int i=0,p;i<len[w];i++) {
				p = anc[w][i]; tmp.x = rod[w][i];
				itr = lower_bound(stk[p].rbegin(), stk[p].rend(), tmp);
				if (itr != stk[p].rend() && ret.z < itr->z) 
					ret = *itr;
			}
			return ret.y;
		}
	private:
		void Get_Root(int w, int f) {
			int mx = 0; sum[w] = 1;
			for  (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]] && to[i] != f) {
					Get_Root(to[i], w);
					sum[w] += sum[to[i]];
					mx = max(mx, sum[to[i]]);
				} 
			} 
			mx = max(mx, area_size - sum[w]);
			if (mx < cur_ans) {
				cur_ans = mx;
				root = w;
			}
		} 
		void Build(int w, int sz) {
			vis[w] = 1; anc[w][0] = w;
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]]) {
					area_size = sum[to[i]] < sum[w]? sum[to[i]]: sz - sum[w];
					cur_ans = INF; Get_Root(to[i], w);
					len[root] = len[w] + 1;
					memcpy(anc[root]+1, anc[w], sizeof(anc[w])-4);
					Build(root, area_size);
				}
			}
			for (int i=1;i<len[w];i++)
				rod[w][i] = DIS(w, anc[w][i]);
		}
}NDC;

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); 
	for (int j=1;j<L;j++) 
		for (int i=1;i<=n;i++) 
			fa[i][j] = fa[fa[i][j-1]][j-1];
	NDC.init();
	m = read();
	for (int i=1,v,d,c;i<=m;i++) {
		if (read() == 1) {
			v = read(); d = read();
			NDC.modify(v, d, read(), i);
		} else printf("%d\n",NDC.query(read()));
	}
	return 0;
}

【BZOJ 1095】[ZJOI2007] Hide 捉迷藏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1095
数据生成器:http://paste.ubuntu.com/23659435/
神犇题解:http://blog.csdn.net/PoPoQQQ/article/details/44461423

解题报告

先建出点分树,再考虑维护三种堆
一种堆用来维护到点i的子树中所有点到点i的父亲的距离
然后第二种堆维护每一个儿子的第一种堆的最大值
第三种堆,维护所有第二种堆的最大值

酱紫话,查询之际输出第三个堆的堆顶
修改的话,就暴力在点分树上向上爬,边爬边修改

话说这题真™难写啊!
从上午11:00写到晚上12:00
真是日了哮天犬了!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100000+9;
const int M = N << 1;
const int INF = 1e9;
 
int head[N],to[M],nxt[M],n,m;
char pat[10],sta[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 T = 0;
    to[++T] = v; nxt[T] = head[u]; head[u] = T;
    to[++T] = u; nxt[T] = head[v]; head[v] = T;
}
 
namespace Dynamic_Node_Decomposition{
    #define DND Dynamic_Node_Decomposition
    int cur,root,node_sz,cnt,in[N];
    int fa[N][18],sum[N],dep[N],len[N],vis[N];
    multiset<int> vout,s1[N],s2[N];
    multiset<int>::iterator itr;
     
    namespace Sparse_Table{
        #define ST Sparse_Table
        int _fa[N][18];
         
        inline void init() {
            for (int i=1;i<=17;i++) { 
                for (int j=1;j<=n;j++) { 
                    _fa[j][i] = _fa[_fa[j][i-1]][i-1];
                }
            }
        }
         
        inline int query(int u, int v) {
            int ret = dep[u] + dep[v];
            if (dep[u] < dep[v]) swap(u, v);
            for (int i=17;~i;i--) {
                if (dep[_fa[u][i]] >= dep[v]) {
                    u = _fa[u][i];
                }
            }
            if (u == v) return ret - dep[u] * 2;
            for (int i=17;~i;i--) {
                if (_fa[u][i] != _fa[v][i]) {
                    u = _fa[u][i];
                    v = _fa[v][i];
                }
            }
            return ret - dep[_fa[u][0]] * 2;
        }
    };
     
    void Get_root(int w, int f) {
        sum[w] = 1; int mx = 0;
        for (int i=head[w];i;i=nxt[i]) {
            if (to[i] != f && !vis[to[i]]) {
                Get_root(to[i], w);
                sum[w] += sum[to[i]];
                mx = max(mx, sum[to[i]]);
            }
        }
        mx = max(mx, node_sz - sum[w]);
        if (mx < cur) cur = mx, root = w;
    } inline int Get_Root(int w, int SZ) {
        cur = INF; node_sz = SZ;
        Get_root(w,-1);
        return root;
    }
     
    #define Delete(x, y) itr = x.lower_bound(y), x.erase(itr)
    #define Max(x) (x.size()? itr = x.end(), *--itr : -1)
    inline int Ans(multiset<int> &TMP) {
        if (TMP.size() < 2) return -1;
        else {
            int ret = *--(itr=TMP.end());
            ret += *--itr; 
            if (*itr <= -1) return -1;
            else return ret;
        } 
    }
     
    inline void modify(int w, int ty) {
        if (ty) cnt++; else cnt--;
        for (int i=0;i<len[w];i++) 
            if (sta[fa[w][i]])
                Delete(vout, Max(s2[fa[w][i]]));
        for (int i=len[w]-2,t1,t2,dis,tmp;~i;i--) {
            t1 = fa[w][i]; t2 = fa[w][i+1];
            dis = ST::query(w, t2);
            tmp = Max(s1[t1]);
            if (tmp = (tmp <= dis)) {
            	Delete(vout, Ans(s2[t2]));
        	    Delete(s2[t2], Max(s1[t1]));
			}
            if (!ty) Delete(s1[t1], dis);
            else s1[t1].insert(dis);
            if (tmp) {
				s2[t2].insert(Max(s1[t1]));
    	        vout.insert(Ans(s2[t2]));
			}
        }
        sta[w] ^= ty >= 0;
        for (int i=0;i<len[w];i++)
            if (sta[fa[w][i]]) 
                vout.insert(Max(s2[fa[w][i]]));
    }
     
    inline int query() {
        if (cnt == 0) return -1;
        else if (cnt == 1) return 0;
        else return Max(vout);
    }
     
    void DFS(int w, int f) {
        dep[w] = dep[f] + 1; ST::_fa[w][0] = f;
        for (int i=head[w];i;i=nxt[i]) 
            if (to[i] != f) DFS(to[i], w);
    } void Build(int w, int sz, int sur) {
        Get_Root(w,sz); 
        vis[w=root] = 1;  
        len[w] = len[sur] + 1;
        fa[w][0] = root;
        memcpy(fa[w]+1,fa[sur],sizeof(fa[w])-4);
        for (int i=head[w];i;i=nxt[i]) 
            if (!vis[to[i]]) 
                Build(to[i], sum[to[i]], w);
    } inline void init() {
        Build(1, n, 0);
        DFS(1, 1);
        ST::init();
        fill(sta+1, sta+1+n, 1);
        for (int i=1;i<=n;i++) { 
            s2[fa[i][1]].insert(-1);
            vout.insert(-1);
            vout.insert(-1);
        }
        for (int i=1;i<=n;i++)
            modify(i, -1);
    }
};
 
int main() {
    n = read(); 
    for (int i=1;i<n;i++)
        Add_Edge(read(), read());
    DND::init();
    m = read();
    for (int i=1,p;i<=m;i++) {
        scanf("%s",pat+1);
        if (pat[1] == 'C') {
            p = read();
            if (sta[p]) DND::modify(p, 0);
            else DND::modify(p, 1);
        } else {
            printf("%d\n",DND::query());
        }
    } 
    return 0;
}

原谅我为了好写而各种封装而造成的巨大常数 QwQ

【Codeforces 715C】Digit Tree

相关链接

题目传送门:http://codeforces.com/problemset/problem/715/C
官方题解:http://codeforces.com/blog/entry/47169

解题报告

要求统计树上路径,那么基本上确定是DP或者树分治了
想一想,好像DP的状态不好表示的样子,于是就直接点分治啦!

考虑对于每一个中心,统计经过该点符合要求的路径数
很明显需要将路径剖成两半,一半扔到map里,另一半直接查

但这题还有需要注意的就是如何去掉两段都在同一子树的非法情况
似乎直接像之前一样在子树的根部调用cal()直接剪掉的方法不管用了
于是可以先DFS一遍,统计所有信息
然后再处理每一个子树的时候,先DFS一遍,把该子树的信息给去掉
查询完成之后,再DFS一遍把信息给加回去

Code

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

const int N = 200000 + 9;

int head[N],nxt[N],cost[N],to[N],REV[N];
int n,MOD; LL vout;

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, 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 gcd(int a, LL &x, int b, LL &y) {
	if (!b) {x = 1, y = 0;}
	else {gcd(b,y,a%b,x);y-=a/b*x;}
}

inline int gcd(int a, int b) {
	static LL x,y;
	gcd(a,x,b,y);
	return (x % MOD + MOD) % MOD;
} 

namespace Node_Decomposition{
	#define ND Node_Decomposition
	const int INF = 1e9;
	int tot,node_sz,root,cur;
	int sum[N],dep[N],vis[N];
	map<int,int> cnt;
	
	void Get_Root(int w, int f) {
		sum[w] = 1; int mx = 0;
		for (int i=head[w];i;i=nxt[i]) {
			if (to[i] != f && !vis[to[i]]) {
				Get_Root(to[i], w);
				sum[w] += sum[to[i]];
				mx = max(mx, sum[to[i]]);
			}
		}
		mx = max(mx, node_sz - sum[w]);
		if (mx < cur) cur = mx, root = w;
	}
	
	void DFS(int w, int f, int delta, LL p, int val) {
		cnt[val] += delta; 
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				DFS(to[i], w, delta, p * 10 % MOD, (val + cost[i] * p) % MOD);
			}
		}
	}
	
	void cal(int w, int f, int t, LL val) {
		vout += cnt[(-val*REV[t]%MOD+MOD)%MOD]; 
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				cal(to[i], w, t+1, (val * 10 + cost[i]) % MOD);
			}
		}
	}
	
	void solve(int w, int sz) {
		vis[w] = 1; cnt.clear(); 
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]]) {
				DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
			}
		}
		vout += cnt[0]; cnt[0]++;
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]]) {
				DFS(to[i], w, -1, 10 % MOD, cost[i] % MOD);
				cal(to[i], w, 1, cost[i] % MOD);
				DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
			}
		}
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]]) {
				node_sz = sum[to[i]] > sum[w] ? sz - sum[w] : sum[to[i]];
				cur = INF; Get_Root(to[i], w);
				solve(root, node_sz);
			}
		}
	}
	
	inline void solve() {
		cur = INF; node_sz = n;
		Get_Root(1,1);
		solve(root,n);
	}
};

int main() {
	n = read(); MOD = read();
	for (int i=1,u,v,w;i<n;i++) {
		u = read(); v = read(); w = read();
		Add_Edge(u + 1, v + 1, w);
	}
	REV[0] = 1; REV[1] = gcd(10, MOD);
	for (int i=2;i<=n;i++)
		REV[i] = (LL)REV[i-1] * REV[1] % MOD;
	ND::solve();
	printf("%lld\n",vout);
	return 0;
}

【模板库】树上点分治

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=1468
参考代码:

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

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

int head[N],nxt[M],to[M],cost[M]; 
int n,k,vout;

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

namespace Node_Decomposition{
	#define ND Node_Decomposition
	const int INF = 10000000;
	int vis[N],dep[N],sum[N];
	int tot,cur,num_node,root;

	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(mx, num_node - mx);
		if (mx < cur) root = w, cur = mx;
	}

	void Get_Dep(int w, int f, int bas) {
		for (int i=head[w];i;i=nxt[i]) {
			if (to[i] != f && !vis[to[i]]) {
				dep[++tot] = bas + cost[i];
				Get_Dep(to[i], w, dep[tot]);
			}
		}
	}

	inline int cal(int w, int bas) {
		dep[tot=1] = bas;
		Get_Dep(w, w, bas);
		sort(dep+1, dep+1+tot);
		int r = tot, l = 1, ret = 0;
		while (l < r) {
			while (l < r && dep[l] + dep[r] > k) r--;
			ret += r - l++;
		}
		return ret;
	}

	void solve(int w, int sz) {
		vis[w] = 1; 
		vout += cal(w, 0);
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]]) {
				vout -= cal(to[i], cost[i]);
				num_node = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
				cur = INF; Get_Root(to[i], w);
				solve(root, num_node);
			}
		}
	}
	
	void solve() {
		num_node = n; cur = INF; 
		Get_Root(1, 1);
		solve(root, n);
	}
}; 

int main() {
	n = read();
	for (int i=1,u,v,w;i<n;i++) {
		u = read(); v = read(); w = read();
		Add_Edge(u, v, w);
	}
	k = read();
	ND::solve();
	printf("%d",vout);
	return 0;
}