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

【Codeforces 757F】Team Rocket Rises Again

相关链接

题目传送门:http://codeforces.com/problemset/problem/757/F
官方题解:http://codeforces.com/blog/entry/49743
中文题面及题解:https://blog.sengxian.com/solutions/cf-757f

解题报告

先搞出一个最短路径树,然后把一些非树边也给搞进来
我们发现这货是一个DAG,那么问题就转化为了:

给定一个DAG,问删掉一个点,最多使得多少点不可到达

然后我们就会想起这个题:BZOJ 2851
于是我们搞一个灾难树就可以啦!

Code

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

const int N = 200000+9;
const int M = 600000+9;
const LL INF = 1e9 * 1e9;

LL dis[N];
int n,m,s,E,vout,fa[N][20],done[N],in[N];
int head[N],to[M],nxt[M],cost[M],dep[N]; 
priority_queue<pair<LL,int> > que;
vector<int> anc[N],son[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, int c = 0) {
	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 void Dijkstra() {
	memset(dis,60,sizeof(dis)); 
	dis[s] = 0; que.push(make_pair(0, s));
	
	while (!que.empty()) {
		int w = que.top().second; que.pop(); 
		if (!done[w]) done[w] = 1;
		else continue;
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] > dis[w] + cost[i]) {
				dis[to[i]] = dis[w] + cost[i];
				que.push(make_pair(-dis[to[i]], to[i]));
			}
		}
	}
}

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

void solve(int w) {
	done[w] = 1;
	int f = anc[w][0];
	for (int i=1;i<(int)anc[w].size();i++) 
		f = LCA(f, anc[w][i]);
	Add_Edge(f, w);
	fa[w][0] = f; dep[w] = dep[f] + 1;
	for (int i=1;i<20;i++)
		fa[w][i] = fa[fa[w][i-1]][i-1];
	for (int i=son[w].size()-1,t;~i;i--) {
		t = son[w][i];
		if (--in[t] == 0 && !done[t]) {
			solve(t);
		}
	}
}

int DFS(int w, int f) {
	int sz = 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			sz += DFS(to[i], w);
		}
	}
	if (w != s) vout = max(vout, sz);
	return sz;
}

int main() {
	n = read(); m = read(); s = read();
	for (int i=1,u,v;i<=m;i++) {
		u = read(); v = read();
		Add_Edge(u, v, read());
	}
	Dijkstra(); 
	for (int w=1;w<=n;w++) {
		if (dis[w] > INF) continue;
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] == dis[w] + cost[i]) {
				anc[to[i]].push_back(w);
				son[w].push_back(to[i]);
				in[to[i]] += (w != s);
			}
		}
	}
	memset(head,0,sizeof(head));
	memset(done,0,sizeof(done));
	done[s] = 1; E = 0;
	for (int i=0;i<20;i++) fa[s][i] = s;
	for (int i=1;i<=n;i++) {
		if (!in[i] && !done[i] && dis[i] < INF) {
			solve(i);
		}
	}
	DFS(s, s);
	printf("%d\n",vout);
	return 0;
}

【BZOJ 4144】[AMPPZ2014] Petrol

相关链接

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

解题报告

随便想一想,这题似乎除了有加油站的点之外,其他点似乎完全可以不用考虑?
再仔细想一想的话,我们似乎只要求出任意两个有加油站的点的最短路,然后再做一个MST就可以了!

现在的问题就是如何求出任意两点的最短路了
我们考虑放宽一点条件,求出一些最短路径的集合 $\{ e \}$ ,使其能够凑出任意两点的最短路
现在考虑两点之间最短路的性质:

定义$blg(x)$表示离$x$最近的关键点
那么对于 $a \to b$ 最短路上,一定是前一部分$blg(x)=a$,后一部分$blg(x)=b$
于是我们就可以通过枚举原图中的一条边$(x_1,x_2)$并且判断$blg(x_1)$是否等于$blg(x_2)$来找到所有中途不经过加油站的最短路

如何证明呢?考虑反证法:如果中途有一个点$blg(y)=c$那么先从$a \to b \to c$一定不比$a \to b$劣
这是因为如果我们走到y点后绕道到c点去加油,回来的时候油量一定不少于从a点到y点的油量

这样我们就可以找到一个边集 $\{ \varepsilon \}$使得 $\{ e\} \subset \{ \varepsilon \}$
于是我们把$\{ \varepsilon \}$拿出来,做一个最小生成树,然后查询的时候,在树上倍增一下就可以啦!

【BZOJ 2001】[HNOI2010] City 城市建设

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2001
神犇题解Ⅰ:http://www.cnblogs.com/BLADEVIL/p/3512644.html
神犇题解Ⅱ:http://blog.miskcoo.com/2015/04/bzoj-2001

解题报告

如果没有边权,只需要维护连通性
那么搞一个可以撤销的并查集就可以啦!

现在考虑带边权的情况,我们仍然对时间进行分治
在每一层,我们进行两个操作:

1. Contraction 缩小点的规模

将所有当前分治区间内会被修改的边的边权置为 $-INF$
然后做一遍MST,将此时通过非 $-INF$ 连接的点用并查集缩起来
因为$-INF$边只会有区间长度个,所以每一次分治后,点的规模不会超过分治区间的长度

2. Reduction 缩小边的规模

将会被修改的边的边权置为 $INF$,然后再做一遍MST
将此时不在MST中的边删去,因为保留的边数不会超过点数,所以边的规模也不会超过分治区间的长度

所以时间复杂度写出来长这样: $T(n) = 2T(\frac{n}{2}) + n\log n$
用主定理化简之后,时间复杂度就是: $O(n{\log ^2}n)$

【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)}$ 个区间
于是树链剖分暴力搞一搞就可以辣!
时空复杂度比之前的做法应该要稍微优越一点

【AtCoder】[CODE FESTIVAL 2016 Final G] Zigzag MST

相关链接

题目传送门:http://cf16-final.contest.atcoder.jp/tasks/codefestival_2016_final_g
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/01/atcoder_codefestival_2016_final_g.pdf

解题报告

这题好神啊!现在感觉每道题都好神啊!

先来看任意一个连边操作:

考虑正常的最小生成树算法,如果用到了价值为 $ c+1$ 的边,那么价值为 $ c$ 的边一定已经考虑过了
于是我们就可以把图等价地变换为下面这个样子:

这样的话,我们可以把价值为 $ c$ 地那一类边拿出来单独考虑
余下的边搞一个堆,连一圈
这样的话,我们的图就改造成了这个样子:

此时我们的边就只剩 $ N+Q$ 条了,直接跑最小生成树算法就可以啦!

Code

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

const int N = 400000+9;

struct Edge{int u,v,w;}e[N];
struct Operation{int p,c;}op[N];
priority_queue<Operation> que;
int n,m,tot,vis[N],fa[N]; LL vout;

inline bool operator < (const Edge &A, const Edge &B) {return A.w < B.w;}
inline bool operator < (const Operation &A, const Operation &B) {return A.c > B.c;}

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 int find(int w) {
	int f = fa[w], tmp;
	while (f != fa[f]) f = fa[f];
	while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
	return f;
}

int main() {
	n = read(); m = read();
	for (int i=1,a,b,c;i<=m;i++) {
		a = read(); b = read(); c = read();
		e[++tot] = (Edge){a, b, c};
		que.push((Operation){a, c+1});
		que.push((Operation){b, c+2});
	}
	while (!que.empty()) {
		Operation w = que.top(); que.pop();
		if (!vis[w.p]) {
			vis[w.p] = 1;
			e[++tot] = (Edge){w.p, (w.p+1)%n, w.c};
			que.push((Operation){(w.p+1)%n, w.c+2});
		}
	}
	sort(e+1, e+1+tot);
	for (int i=0;i<=n;i++) fa[i] = i;
	for (int i=1;i<=tot;i++) {
		if (find(e[i].u) != find(e[i].v)) {
			fa[fa[e[i].u]] = fa[e[i].v];
			vout += e[i].w;
		}
	}
	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;
}

【BZOJ 3924】[ZJOI2015] 幻想乡战略游戏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3924
神犇题解:http://www.cnblogs.com/clrs97/p/4779754.html
官方题解:http://wjmzbmr.com/archives/zjoi-2015-day-1题解/

解题报告

考虑从根开始向下走
如果一个儿子的子树的权值和大于总和的一半
那么所求的点一定在这个儿子的子树中
由此可见,实际上我们所求的是这样的点:

深度最大的,子树权值和大于总权值和一半的点

这样的话,暴力找复杂度不稳定
考虑树链剖分的话,可以在\({\log ^2}(n)\)的时间复杂度内找到答案
最后考虑输出解的话,似乎直接用树链剖分不行的样子
于是似乎还得用一个点分治? (・∀・(・∀・(・∀・*)

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 = 18;
const int INF = 1e9;

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

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

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

class Heavy_Light_Decomposition{
	int dep[N],dis[N],fa[N],top[N],sz[N];
	int go[N],pos[N],len[N],sum,cnt;
	vector<int> que[N];
	class Fenwick_Tree{
		#define lowbit(x) ((x)&-(x))
		int arr[N];
		public:
			inline void modify(int l, int r, int delta) {
				modify(l-1, -delta);
				modify(r, delta);
			}
			inline int query(int p) {
				LL ret = 0;
				for (int i=p;i<=n;i+=lowbit(i))
					ret += arr[i];
				return ret;
			}
		private:
			inline void modify(int p, int delta) {
				for (int i=p;i;i-=lowbit(i))
					arr[i] += delta;
			}
	}BIT;
	public:
		inline void init() {
			DFS1(1, 1);
			DFS2(1, 1, 1);
		}
		inline int DIS(int u, int v) {
			int lca = LCA(u, v);
			return dis[u] + dis[v] - (dis[lca] << 1);	
		}
		inline void modify(int w, int v) {
			sum += v;
			for (;w;w=fa[top[w]]) 
				BIT.modify(pos[top[w]], pos[w], v);
		}
		inline int query() {
			int w = 1, tag = 1;
			while (tag) {
				int l = 1, r = len[w]-1, mid, ret = 0;
				while (l <= r) {
					mid = l + r >> 1;
					if (BIT.query(pos[que[w][mid]])*2 <= sum) r = mid - 1;
					else l = mid + 1, ret = mid;
				} 
				w = que[w][ret]; tag = 0;
				for (int i=head[w];i;i=nxt[i]) {
					if (dep[to[i]] > dep[w] && BIT.query(pos[to[i]])*2 > sum) {
						tag = 1; w = to[i]; break;
					}
				}
			}
 			return w;
		}
	private:
		void DFS1(int w, int f) {
			sz[w] = 1; 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];
					fa[to[i]] = w;
					DFS1(to[i], w);
					sz[w] += sz[to[i]];
					if (sz[to[i]] > sz[go[w]])
						go[w] = to[i];
				}
			}
		}
		void DFS2(int w, int f, int t) {
			que[t].push_back(w);
			top[w] = t;	pos[w] = ++cnt;
			if (go[w]) DFS2(go[w], w, t);
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && to[i] != go[w]) {
					DFS2(to[i], w, to[i]);
				}
			}
			len[w] = que[w].size();
			que[w].push_back(w);
		}
		inline int LCA(int u, int v) {
			while (top[u] != top[v]) 
				if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
				else v = fa[top[v]];
			return dep[u] > dep[v]? v: u;
		}
}HLD;

class Vertex_Based_Divide_and_Conquer{
	int sum[N],vis[N],len[N],fa[N][L],rod[N][L];
	int root,size,cur,val_sum[N],val_sum_del[N];
	LL part_ans[N],part_ans_del[N];
	public:
		inline void init() {
			int rt = Get_Root(1, n);
			len[rt] = 1;
			build(rt, n);
		}
		inline void modify(int w, int v) {
			val_sum[w] += v;
			for (int i=1,p=w,d,u;i<len[w];i++) {
				u = p; p = fa[w][i]; d = rod[w][i];
				val_sum[p] += v;
				val_sum_del[u] += v;
				part_ans[p] += (LL)v * d;
				part_ans_del[u] += (LL)v * d;
			}
		}
		inline LL query(int w) {
			LL ret = part_ans[w];
			for (int i=1,p=w,u,d;i<len[w];i++) {
				u = p; p = fa[w][i]; d = rod[w][i];
				ret += part_ans[p] + (LL)val_sum[p] * d;
				ret -= part_ans_del[u] + (LL)val_sum_del[u] * d;
			}
			return ret;
		} 
	private:
		inline int Get_Root(int w, int sz) {
			size = sz; cur = INF;
			Get_root(w, w);
			return root;
		}
		void Get_root(int w, int f) {
			int mx = 1; 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, size - sum[w]);
			if (mx < cur) cur = mx, root = w;
		}
		void build(int w, int sz) {
			vis[w] = 1; fa[w][0] = w;
			for (int i=1;i<len[w];i++) 
				rod[w][i] = HLD.DIS(w, fa[w][i]);
			for (int i=head[w],tmp,rt;i;i=nxt[i]) {
				if (!vis[to[i]]) {
					tmp = sum[to[i]]<sum[w]? sum[to[i]]: sz-sum[w];
					rt = Get_Root(to[i], tmp);
					len[rt] = len[w] + 1;
					memcpy(fa[rt]+1, fa[w], sizeof(int)*len[w]);
					build(rt, tmp);
				}
			}
		}
		
}VDC;

int main() {
	n = read(); m = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		Add_Edge(u, v, read());
	}
	HLD.init();
	VDC.init();
	for (int i=1,p,v;i<=m;i++) {
		p = read(); v = read();
		HLD.modify(p, v);
		VDC.modify(p, v);
		p = HLD.query();
		printf("%lld\n",VDC.query(p));
	}
	return 0;
}

【HDU 5571】tree

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5571
数据生成器:http://paste.ubuntu.com/23672970/
中文题面:http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=651&pid=1004
官方题解:http://oi.cyo.ng/?attachment_id=2084

解题报告

看到位运算,首先想到的就是一位一位独立来搞
酱紫的话,这题就非常简单了
直接上点分树,什么数据结构都不用套,记录零一就可以了

值得注意的是,拆二进制最好拆在最外层
因为拆在里面的话,数组会多一维,寻址的时间消耗大大增加
否则会T到死,不要问我是怎么知道的

Code

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

const int N = 30000+9;
const int M = N << 1;
const int L = 16;
const int INF = 1e9;

int n,m,T,head[N],to[M],nxt[M],cost[M],ori[N];
int val[N],dep[N],dis[N],fa[N][L],P[N],V[N];
LL ans[N];

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

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

void DFS(int w, int f) {
	dep[w] = dep[f] + 1;
	fa[w][0] = f;
	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 LCA(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i=L-1;~i;i--) {
		if (dep[fa[u][i]] >= dep[v]) {
			u = fa[u][i];
		}
	}
	if (u == v) return u;
	for (int i=L-1;~i;i--) {
		if (fa[u][i] != fa[v][i]) {
			u = fa[u][i];
			v = fa[v][i];
		}
	}
	return fa[u][0];
}

inline int DIS(int u, int v) {
	int lca = LCA(u, v);
	return dis[u] + dis[v] - dis[lca] * 2;
}

class Node_Based_Divide_and_Conquer{
	int area_sz,cur_ans,root,rod[N][L],sum[N];
	int anc[N][L],len[N],tos[2][N],tot[2][N];
	bool vis[N]; LL f[2][N],sub[2][N];
	
	public:
		inline void init() {
			memset(vis,0,sizeof(vis));
			cur_ans = INF; area_sz = n;
			Get_Root(1, 1); len[root] = 1;
			Build(root, n);
		}
		
		inline void prework() {
			memset(f, 0 ,sizeof(f));
			memset(sub, 0, sizeof(sub));
			memset(tot, 0, sizeof(tot));
			memset(tos, 0, sizeof(tos));
		}
		
		inline void modify(int w, int t, int p) {
			for (int i=0,pre,cur;i<len[w];i++) {
				cur = anc[w][i];
				f[t][cur] += rod[w][i] * p;
				tot[t][cur] += p;
				if (i) {
					pre = anc[w][i-1];
					sub[t][pre] += rod[w][i] * p;
					tos[t][pre] += p;
				}
			}
		}
		
		inline LL query(int w, int t, int k) {
			LL ret = 0,s,d; t ^= 1;
			ret += f[t][w] << k;
			for (int i=1,cur,pre;i<len[w];i++) {
				cur = anc[w][i]; pre = anc[w][i-1];
				d = f[t][cur] - sub[t][pre];
				s = tot[t][cur] - tos[t][pre];
				ret += d + s * rod[w][i] << k;
			}
			return ret;
		} 
	private:
		void Get_Root(int w, int F) {
			sum[w] = 1; int mx = 0;
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]] && to[i] != F) {
					Get_Root(to[i], w);
					mx = max(sum[to[i]], mx);
					sum[w] += sum[to[i]];
				}
			}
			mx = max(mx, area_sz - 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_sz = 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(int)*len[w]);
					Build(root, area_sz);
				}
			}
			for (int i=0;i<len[w];i++)
				rod[w][i] = DIS(w, anc[w][i]);
		}
}NDC;

int main() {
	for (LL vout=0;~scanf("%d",&n);vout=T=0) {
		memset(head,0,sizeof(head));
		memset(ans,0,sizeof(ans));
		for (int i=1;i<=n;i++) 
			ori[i] = read();
		for (int i=1,u,v,w;i<n;i++) {
			u = read(); v = read(); w = read();
			Add_Edge(u, v, w);
		}	
		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;i<=m;i++) {
			P[i] = read();
			V[i] = read();
		}
		for (int j=0;j<L;j++,vout=0) {
			memcpy(val,ori,sizeof(ori));
			NDC.prework();
			for (int i=1;i<=n;i++) {
				val[i] >>= j; val[i] &= 1;
				NDC.modify(i, val[i], 1);
				vout += NDC.query(i, val[i], j);
			}
			for (int i=1,p,v;i<=m;i++) {
				p = P[i]; v = (V[i] >> j) & 1;
				vout -= NDC.query(p, val[p], j);
				NDC.modify(p, val[p], -1);
				NDC.modify(p, v, 1);
				vout += NDC.query(p, val[p] = v, j);
				ans[i] += vout;
			}
		}
		for (int i=1;i<=m;i++)
			printf("%I64d\n",ans[i]);
	} 
	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;
}