点分治&&DSU on tree学习笔记-爱代码爱编程
点分治
题目描述
给定一棵有 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
题意
点 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