搭建单位网站,网站建设在电子商务中的作用,WordPress密码如何修改,信息型网站文章目录前言点分治背景解析代码点分树情境代码thanks for reading!所谓点分治#xff0c;就是把所有的点分开来治 #xff08;逃#xff09; #xff08;应广大观众要求#xff0c;开篇废话改回原风格qwq#xff09;
前言
很神奇的算法。 没有引入任何新的知识#x…
文章目录前言点分治背景解析代码点分树情境代码thanks for reading!所谓点分治就是把所有的点分开来治 逃 应广大观众要求开篇废话改回原风格qwq
前言
很神奇的算法。 没有引入任何新的知识却把时间复杂度降到了一个很好的等级。 感觉点分治模板本身当成一道题来做也不过分。
对于点分树感觉它的另一个名字也很不错动态点分治。 通常可以解决一些与树原形态联系较小的问题如距离等。
点分治
背景 给定一棵树求树上距离不超过k的点对数目 n≤105n\leq10^5n≤105 传送门
解析
考虑点分治
分治的普遍特征是把总问题分解成若干子问题递归求解再合并答案 本题中不难想到按照重心把子树分成若干个联通块进行递归这样划分次数不会超过log级别 现在的重点就是如何合并答案 首先各个联通块的答案肯定要加起来 剩下还没统计到的就是 经过重心设为x 的合法路径了
考虑把所有点dfs一遍算出深度sort一下后利用双指针就可以线性求出来
比较敏锐的童鞋很显然会发现我这纯粹就是胡说八道因为这样还会重复统计到在同一个子树内的答案 所以我们要把在同一个子树内的答案容斥掉 代码实现上计算答案和容斥部分可以通过传参的不同用一个函数进行 具体实现很优雅看代码应该能更好的理解
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N4e4100;
const int M2e510500;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m;
struct node{int to,nxt,w;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y,int w){p[cnt](node){y,fi[x],w};fi[x]cnt;return;
}int siz[N],mx[N],dis[N],tot,rt,S,ans;
bool vis[N];void find(int x,int fa){siz[x]1;mx[x]0;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(vis[to]||tofa) continue;find(to,x);siz[x]siz[to];mx[x]max(mx[x],siz[to]);}mx[x]max(mx[x],S-siz[x]);if(!rt||mx[x]mx[rt]) rtx;return;
}void getdis(int x,int fa,int d){dis[tot]d;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tofa||vis[to]) continue;getdis(to,x,dp[i].w);}return;
}int calc(int x,int d){tot0;getdis(x,0,d); sort(dis1,dis1tot);int l1,rtot,res(0);while(lr){if(dis[l]dis[r]m) resr-l,l;else --r;}return res;
}void solve(int x){Ssiz[x];rt0;find(x,0);xrt;anscalc(x,0);vis[x]1;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(vis[to]) continue;ans-calc(to,p[i].w);}for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(vis[to]) continue;solve(to);}return;
}int main(){
#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);
#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();for(int i1;in;i){int xread(),yread(),wread();addline(x,y,w);addline(y,x,w);}mread();Sn;find(1,0);siz[rt]n;solve(rt);printf(%d\n,ans);return 0;
}
/*
4 4 1 2 3 4 7
*/
点分树
情境 给出一棵点带权边无权的树要求你支持在线回答到某个点距离不超过 kkk 的点对权值和或者修改某个点对权值。 其实所有的分治算法都形成了一个树形结构那么这里我们考虑把之前的点分治的结构显性的建出来。 具体的每一层的重心都是下一层重心的父亲。 这样我们就建出来点分树它的树高是 O(logn)O(\log n)O(logn) 的。
对于每次对 xxx 结点的询问我们就先统计 xxx 自己处的信息距离不超过 kkk 的权值和然后不停往上跳 fafafa然后统计 fafafa 的信息与 fafafa 距离不超过 k−dis(fa,x)k-dis(fa,x)k−dis(fa,x) 的权值和。 那么对应的我们就需要每个结点维护两个数据结构一个维护自己的信息一个维护对父亲的贡献。这是一个很重要的套路 具体的说维护两个树状数组一个维护点分树上的子树内到自己距离为 xxx 的权值和一个维护点分树上的子树内到父亲距离为 xxx 的权值和。
然而我们是无法对每个结点开大小为 O(n)O(n)O(n) 的数组的所以我们考虑使用 vector只开到 O(sizx)O(siz_x)O(sizx) 大小这样空间复杂度就是 O(nlogn)O(n\log n)O(nlogn) 的。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define OK printf(ok\n)
#define debug(...) fprintf(stderr,__VA_ARGS__)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N2e5100;
const int inf1e9100;
int n,m;
struct node{int to,nxt;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;return;
}
int dep[N],q[N1],tot,pl[N];
void dfs0(int x,int f){dep[x]dep[f]1;q[tot]x;pl[x]tot;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;dfs0(to,x);q[tot]x;}return;
}
int Min(int x,int y){return dep[x]dep[y]?x:y;
}
int lg[N1],mn[N1][20],mi[20];
void init(){dfs0(1,0);lg[0]-1;for(int i1;itot;i) lg[i]lg[i1]1;mi[0]1;for(int i1;ilg[tot];i) mi[i]mi[i-1]1;for(int i1;itot;i) mn[i][0]q[i];for(int k1;klg[tot];k){for(int i1;imi[k]-1tot;i) mn[i][k]Min(mn[i][k-1],mn[imi[k-1]][k-1]);}return;
}
inline int Lca(int x,int y){xpl[x];ypl[y];if(xy) swap(x,y);int klg[y-x1];//printf( k%d\n,k);return Min(mn[x][k],mn[y-mi[k]1][k]);
}
inline int Dis(int x,int y){int lcaLca(x,y);//printf((%d %d) lca%d dis%d\n,x,y,lca,dep[x]dep[y]-2*dep[lca]);return dep[x]dep[y]-2*dep[lca];
}
vectorintf[2][N];
int w[N],top[N];
int rt,mnn,siz[N],S,son[N];
bool vis[N];
int o;
void findrt(int x,int f){siz[x]1;son[x]0;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof||vis[to]) continue;findrt(to,x);siz[x]siz[to];son[x]max(son[x],siz[to]);}son[x]max(son[x],S-siz[x]);if(mnnson[x]){mnnson[x];rtx;}return;
}
int tim;
int solve(int x,int nS){//if(tim%10000) debug(%d\n,x);//printf(??\n);SnS;mnninf;findrt(x,0);xrt;vis[x]1;siz[x]S1;f[0][x].resize(siz[x]1);f[1][x].resize(siz[x]1);for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(vis[to]) continue;int tmpsolve(to,nS-son[to]);top[tmp]x;}return x;
}
void add(int op,int x,int p,int w){p;for(;psiz[x];pp-p){f[op][x][p]w;//printf(%d\n,p);}return;
}
int ask(int op,int x,int p){if(p0) return 0;p;pmin(p,siz[x]);int res(0);for(;p;p-p-p) resf[op][x][p];return res;
}
void upd(int x,int w){//w:deltafor(int ix;i;itop[i]) add(0,i,Dis(x,i),w);for(int ix;top[i];itop[i]) add(1,i,Dis(x,top[i]),w);return;
}
int query(int x,int d){int ansask(0,x,d);//printf(ans%d\n,ans);for(int ix;top[i];itop[i]){int ndd-Dis(x,top[i]);//printf(top%d nd%d ans%d-%d%d\n,top[x],)ansask(0,top[i],nd)-ask(1,i,nd);}return ans;
}
signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();mread();for(int i1;in;i) w[i]read();for(int i1;in;i){int xread(),yread();addline(x,y);addline(y,x);}init(); solve(1,n);/*mnninf;Sn;findrt(1,0);mnn0;findrt(rt,0); solve(rt);*/ //return 0;for(int i1;in;i) upd(i,w[i]);//for(int i1;in;i) printf(i%d siz%d top%d\n,i,siz[i],top[i]);int lst(0);for(int i1;im;i){int opread(),xread()^lst,yread()^lst;if(op1){upd(x,y-w[x]);w[x]y;}else{printf(%d\n,lstquery(x,y));}}return 0;
}
/*
7 1
1 2 3 4 5 6 7
1 2
2 3
2 4
4 5
4 6
1 7
0 7 1
*/
thanks for reading!
