没有网站可以做京东联盟吗,网站建设的招标文件,手机页面设计软件,百度信息流广告投放正题
题目链接:https://www.luogu.com.cn/problem/P6329 解题思路
给出nnn个点的一棵树#xff0c;每个点有权值#xff0c;有mmm次操作
修改一个点xxx的权值为yyy询问距离点xxx不超过kkk的所有点点权和 解题思路
点分树的模板题#xff0c;先点分治构造出点分树#x…正题
题目链接:https://www.luogu.com.cn/problem/P6329 解题思路
给出nnn个点的一棵树每个点有权值有mmm次操作
修改一个点xxx的权值为yyy询问距离点xxx不超过kkk的所有点点权和 解题思路
点分树的模板题先点分治构造出点分树然后在上面维护信息。
对于每个点维护一个点分子树内与该点的距离为下标点权为权值的的树状数组然后查询的时候直接查距离不超过k−dis(now,x)k-dis(now,x)k−dis(now,x)的就好了。
发现与点分父节点会有算重的情况这个时候顺便维护一个以与父节点的距离为下标的树状数组然后减去重复的答案就好了。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n)。 code
#includecstdio
#includecstring
#includealgorithm
#includevector
#define lowbit(x) (x-x)
using namespace std;
const int N1e510,T18,inf1e9;
struct node{int to,next;
}a[N1];
int n,m,tot,cnt,num,root,fr,val[N];
int ls[N],f[N1][T],rfn[N],dep[N];
int fa[N],siz[N],lg[N1],mx;
bool v[N];
struct BIT{vectorint t;int n;void Init(int x){x;t.resize(x);nx;return;}void Change(int x,int val){x;while(xn){t[x-1]val;xlowbit(x);}return;}int Ask(int x){if(x0)return 0;int ans0;x;if(xn)xn;while(x){anst[x-1];x-lowbit(x);}return ans;}
}s1[N],s2[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x,int fa){dep[x]dep[fa]1;f[cnt][0]x;rfn[x]cnt;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dfs(y,x);f[cnt][0]x;}return;
}
void groot(int x,int fa){siz[x]1;int f0;for(int ils[x];i;ia[i].next){int ya[i].to;if(v[y]||yfa)continue;groot(y,x);siz[x]siz[y];fmax(f,siz[y]);}fmax(f,num-siz[x]);if(ffr)rootx,frf;return;
}
void calc(int x,int fa,int dep){mxmax(mx,dep);for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||v[y])continue;calc(y,x,dep1);}return;
}
void Build(int x,int h){v[x]1;int Snum,zfr;mx0;calc(x,x,0);s1[x].Init(mx);s2[x].Init(h);for(int ils[x];i;ia[i].next){int ya[i].to;if(v[y])continue;num(siz[y]siz[x])?(S-siz[x]):siz[y];mx0;calc(y,x,1);frinf;groot(y,x);yroot;fa[y]x;Build(y,mx);}return;
}
void Init(){dfs(1,1);for(int i2;icnt;i)lg[i]lg[i1]1;for(int j1;(1j)cnt;j)for(int i1;i(1j)-1cnt;i){int xf[i][j-1],yf[i(1j-1)][j-1];f[i][j](dep[x]dep[y])?x:y;}frinf;numn;groot(1,1);Build(root,0);return;
}
int LCA(int l,int r){lrfn[l];rrfn[r];if(lr)swap(l,r);int zlg[r-l1];int xf[l][z],yf[r-(1z)1][z];return (dep[x]dep[y])?x:y;
}
int dis(int x,int y)
{return dep[x]dep[y]-2*dep[LCA(x,y)];}
void Updata(int x,int val){int nowx;while(now){s1[now].Change(dis(now,x),val);if(fa[now])s2[now].Change(dis(fa[now],x),val);nowfa[now];}return;
}
int Ask(int x,int k){int ans0,nowx;anss1[x].Ask(k);while(fa[now]){int ddis(fa[now],x);anss1[fa[now]].Ask(k-d);if(fa[now])ans-s2[now].Ask(k-d);nowfa[now];}return ans;
}
int main()
{// freopen(P6329_1.in,r,stdin);// freopen(data.out,w,stdout);scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,val[i]);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}Init();for(int i1;in;i)Updata(i,val[i]);int last0;while(m--){int op,x,y;scanf(%d%d%d,op,x,y);x^last;y^last;if(op){Updata(x,y-val[x]);val[x]y;}elseprintf(%d\n,lastAsk(x,y));}return 0;
}
