代码编织梦想

点分治

luoguの模板

题目描述

给定一棵有 n n n 个点的树,询问树上距离为 k k k 的点对是否存在。

思路

递归处理每一个子树,容斥消除重复的答案,复杂度取决于递归的深度。
考虑每次选子树重心作为根,复杂度 O ( n m   l o g   n ) O(nm \ log \ n) O(nm log n)

代码

#include<bits/stdc++.h>
#define ll long long
#define N 10005
#define W 10000005
#define rep(i,a,n) for (register int i=a;i<=n;i++)
#define per(i,a,n) for (register int i=n;i>=a;i--)
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define lowbit(i) ((i)&(-i))
#define VI vector<int>

using namespace std;
int n,m,u,v,w,ans[W],root,f[N],size[N],dis[N],sum,tot,cnt,head[N];
bool vis[N];
inline int read(){
	int s=0,w=1;char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') w = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		s = (s<<1)+(s<<3)+ch-'0';
		ch = getchar();
	}
	return s*w;
}
struct edge{
	int to,next,w;
	edge(){}
	edge(int a,int b,int c){to = a;next = b;w = c;}
}e[N<<1];
inline void add(int u,int v,int w){
	e[++cnt] = edge(v,head[u],w);
	head[u] = cnt;
}
void Getroot(int u,int fa){
	f[u] = 0,size[u] = 1;
	for(int i = head[u];i;i = e[i].next){
		int v = e[i].to;
		if(vis[v]||v == fa) continue;
		Getroot(v,u);
		size[u] += size[v];
		f[u] = max(f[u],size[v]);
	}
	f[u] = max(f[u],sum-size[u]);
	if(f[root] > f[u]){
		root = u;
	}
}
void Getdis(int u,int len,int fa){
	dis[++tot] = len;
	for(int i = head[u];i;i = e[i].next){
		int v = e[i].to;
		if(vis[v]||v == fa) continue;
		Getdis(v,len+e[i].w,u);
	}
}
inline void calc(int u,int len,int val){
	tot = 0;
	Getdis(u,len,0);
	rep(i,1,tot){
		rep(j,1,tot){
			if(dis[i]+dis[j] > 10000000||i == j) continue;
			ans[dis[i]+dis[j]] += val;
		}
	}
}
void divide(int u){
	vis[u] = 1;
	calc(u,0,1);
	for(int i = head[u];i;i = e[i].next){
		int v = e[i].to;
		if(vis[v]) continue;
		calc(v,e[i].w,-1);
		root = 0;sum = size[v];
		Getroot(v,0);
		divide(root);
	}
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	//memset(head,-1,sizeof head);
	n = read();m = read();
	rep(i,2,n){
		u = read();v = read();w = read();
		add(u,v,w);
		add(v,u,w);
	}
	sum = f[0] = n;
	Getroot(1,0);
	divide(root);
	while(m--){
		u = read();
		if(ans[u]>0) 
			printf("AYE\n");
		else
			printf("NAY\n");
	}
	return 0;
}

(未完待续)

DSU ON TREE

Lomsat gelral

Link

题意

i i i有一个颜色 c i c_i ci,求每个 i i i的子树中出现出现次数最多的颜色,如有多种,求 ∑ c i \sum{c_i} ci

思路

依旧是暴力递归处理,但先做一遍轻重链剖分,求出每个点的重儿子。对于轻儿子,暴力递归并消除影响,对于重儿子,求答案后保留,以优化复杂度。

代码
#include<bits/stdc++.h>
#define int long long
#define N 100015
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define lowbit(i) ((i)&(-i))
#define VI vector<int>
using namespace std;
int n,c[N],u,v,size[N],son[N],Mx,Son,cnt[N],sum,ans[N];
VI e[N];
void dfs(int u,int fa){
	int Max = 0;
	size[u] = 1;
	for(auto v:e[u]){
		if(v==fa) continue;
		dfs(v,u);
		size[u] += size[v];
		if(size[v] > Max){
			Max = size[v];
			son[u] = v;
		}
	}
}
void add(int u,int fa,int val){
	cnt[c[u]] += val;
	if(cnt[c[u]] > Mx){
		Mx = cnt[c[u]];
		sum = c[u];
	}else if(cnt[c[u]] == Mx){
		sum += c[u];
	}
	for(auto v:e[u]){
		if(v==fa||v==Son) continue;
		add(v,u,val);
	}
}
void dfs2(int u,int fa,int opt){
	for(auto v:e[u]){
		if(v==fa) continue;
		if(v != son[u]) dfs2(v,u,0);
	}
	if(son[u]) dfs2(son[u],u,1),Son = son[u];
	add(u,fa,1);Son = 0;
	ans[u] = sum;
	if(!opt) add(u,fa,-1),sum = Mx = 0;
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%lld",&n);
	rep(i,1,n) scanf("%lld",&c[i]);
	rep(i,2,n){
		scanf("%lld%lld",&u,&v);
		e[u].pb(v);e[v].pb(u);
	}
	dfs(1,0);
//	puts("YES");
	// for(auto v:e[1]) cout << v << ' ';
	// cout << endl;
	dfs2(1,0,0);
	rep(i,1,n) printf("%lld ",ans[i]);
	return 0;
}

(未完待续)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/qq_44062973/article/details/107937914