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

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

【BZOJ 1468】Tree

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1468
主定理相关:http://raytaylorlin.com/Tech/algorithm/master-method/
神犇题解:http://www.cnblogs.com/iwtwiioi/p/4172279.html

题解

就是点分治的模板题啊!
另外关于主定理的话,我觉得这个式子说得很清楚:
若 $T(n) \le aT({n \over b}) + O({n^d})$
则 \(T(n) = \begin{cases} O(n^d \log n) & a = {b^d} \cr O(n^d) & a < {b^d} \cr O({n^{ { {\log }_b }a } }) & a > {b^d} \end{cases}\)

Code

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

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

int head[N],nxt[M],to[M],cost[M],vis[N],dep[N],sum[N]; 
int n,k,tot,cur,num_node,root,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 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);
		}
	}
}

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();
	num_node = n; cur = INF; Get_Root(1, 1);
	solve(root, n);
	printf("%d",vout);
	return 0;
}