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

【BZOJ 2069】[POI2004] ZAW

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2069
数据传送门:http://oi.cyo.ng/wp-content/uploads/2016/10/2069.rar

这题说两个做法:
1)最短路+奇怪的姿势,时间复杂度O(nlogn)
2)关键点间的最短路,时间复杂度O(nlog^2n)

先说第一种方式:
从1开始跑最短路,每个点记录最短路+次短路,保证路径上第二个点不同(1算第一个点)
然后O(n)扫描每一个点,使用最短路+次短路更新答案即可
这种方法虽然时间复杂度较优,但不是很通用

接下来我们说一说关键点间的最短路:
考虑将答案路径与1相连的两条边删掉
路径变为与1相连的点间的最短路径
于是将与1相邻的点设为关键点,跑关键点间的最短路即可

接下来说一说怎么跑关键点间的最短路:
考虑拆二进制,枚举二进制的每一位。
根据这一位是否为1,将关键点分为两个点集
然后一个连超级源,另一个连超级汇即可
时间复杂度O(nlog^2(n))
其实这才是这篇题解的重点

这里是二进制拆分+Dijkatra的代码,请随意食用~

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

const int N = 50000+9;
const int M = 300000+9;
const int INF = 1e9;

int head[N],dis[N],t1[N],t2[N],t3[N],head_tmp[N],tot,TT,S,T,vout=INF,n,m,nxt[M],to[M],cost[M];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que; bool vis[N]; 

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

inline void Add_Edge(int u, int v, int c1, int c2) {
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; cost[TT] = c1;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; cost[TT] = c2;
}

inline int Dijkstra() {
	memset(dis,60,sizeof(dis));
	memset(vis,0,sizeof(vis));
	que.push(make_pair(0,S));
	dis[S] = 0; vis[1] = 1;
	
	while (!que.empty()) {
		int w = que.top().second; que.pop();
		if (vis[w]) continue;
		else vis[w] = 1; 
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] > dis[w] + cost[i] && !vis[to[i]]) {
				dis[to[i]] = dis[w] + cost[i];
				que.push(make_pair(dis[to[i]], to[i]));	
			} 
		}
	}
	return dis[T];
}

int main(){
	n = read(); m = read();
	for (int i=1,a,b,c,d;i<=m;i++) {
		a = read(); b = read();
		c = read(); d = read();
		Add_Edge(a, b, c, d);
		
		if (a == 1) {
			t1[++tot] = b;
			t2[tot] = c;	
			t3[tot] = d;
		} else if (b == 1) {
			t1[++tot] = a;
			t2[tot] = d;
			t3[tot] = c;
		}
	}
	
	S = N - 1; T = N - 2;
	int w = 0, TMP = n, ori = TT;
	while (TMP) w++, TMP >>= 1;
	memcpy(head_tmp,head,sizeof(head));
	
	for (int k=0,cur=1;k<=w;k++,cur<<=1) {
		TT = ori;
		memcpy(head,head_tmp,sizeof(head));
		
		for (int i=1;i<=tot;i++) {
			if (t1[i]&cur) Add_Edge(S,t1[i],t2[i],INF);
			else Add_Edge(t1[i],T,t3[i],INF);
		} 
		vout = min(Dijkstra(), vout);
		
		TT = ori;
		memcpy(head,head_tmp,sizeof(head));
		
		for (int i=1;i<=tot;i++) {
			if (t1[i]&cur) Add_Edge(t1[i],T,t3[i],INF);
			else Add_Edge(S,t1[i],t2[i],INF);
		} 
		vout = min(Dijkstra(), vout);
	}
	printf("%d\n",vout);
	return 0;
}