1.题目大意:
时隔六日,爷终于会了,不就是点分树吗?(有手就行..咦,不对,我手呢?)
来看看这个题目,这个题目是说你有一颗树啊.
然后两个操作.
第一个操作是:
查询u距离不超过k的点权和.
第二个操作是:
修改u的点权.
2.解题思路:
很快啊,大佬很快就会做了,我大意了,看了三天.原来大佬是有备(动态开点)而来.
正题:
首先在学点分树前先学动态开点,lca,虚树,点分治,容斥.学完这些学这个算法就很简单了.因为这个算法就是这些算法的集合.对于这个题目的步骤如下:
1.先dfs一下,处理原树的深度.和预处理f[i][j]倍增数组,表示i这个点,2^j上是哪个点,这里我们拿1当作根节点.然后搜一下就完事.
2.寻找重心.这里同点分治寻找重心是一样的.
3.然后建立一颗虚数,这里同点分治的solve过程类似.虚数的话,你只要开一个dfa[u]表示u的虚数的父节点是哪个就好了.
4.下面就是重点了,我们建一个动态开点的线段树,具体作用是:单点更新,区间查询前缀和的作用.我们对于每个点都开两个线段树(线段树的下标就是距离其他点与这个点的距离,线段树的权值则是点权).第一颗线段树维护的是:虚数下在这个点的节点对于虚数上的点u的贡献(一直可表达到根).第二颗线段树维护的是:虚数上这个点的节点对于它的爷爷dfa[u]的贡献(一直可表达到根).然后由容斥原理可以简单的得到,我这个点的贡献就是第一颗线段树中的贡献-第二颗线段树的贡献.然后就没了~
(确信没讲废话...然后就是手撸代码了)
3.代码
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+3e4,M=19;
int val[N],dep[N],f[N][M];
vector<int>v[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline int lca(int a,int b)//求两个节点的lca.
{
//这个应该可以乱写,确信.首先跳到同深度.
if(dep[b]>dep[a]) swap(a,b);
//把大的放前面,跳小的.ww
for(int i=18;i>=0;i--)
{
if(dep[f[a][i]]>=dep[b]) a=f[a][i];
}if(a==b) return a;
for(int i=18;i>=0;i--)
{
if(f[a][i]!=f[b][i])
{
a=f[a][i];
b=f[b][i];
}
}return f[a][0];
}
inline int dis(int a,int b)
{
return dep[a]+dep[b]-2*dep[lca(a,b)];
}//求两个点的树上距离.
void dfs(int u,int fa,int D)
{
dep[u]=D;f[u][0]=fa;
for(int i=1;i<M;i++)
{
f[u][i]=f[f[u][i-1]][i-1];
}
for(int i=0;i<(int)v[u].size();i++)
{
int x=v[u][i];
if(x!=fa) dfs(x,u,D+1);
}
}//处理原树的深度.
int siz[N],dp[N],root,vis[N];//每个点的子树大小和某个点子树中最大的子树最小是多少.
void f_root(int u,int fa,int tot)
{
siz[u]=1;dp[u]=0;
for(int i=0;i<(int)v[u].size();i++)
{
int x=v[u][i];
if(x==fa||vis[x]) continue;
f_root(x,u,tot);siz[u]+=siz[x];
dp[u]=max(dp[u],siz[x]);
}dp[u]=max(dp[u],tot-siz[u]);
if(dp[u]<dp[root]) root=u;
}
int dfa[N],dsiz[N];//记录当前u节点在虚树上的父亲节点是哪个.重心包含的虚数大小.
void rebuild(int u,int tot)
{
vis[u]=1;dsiz[u]=tot;
for(int i=0;i<(int)v[u].size();i++)
{
int x=v[u][i];
if(vis[x]) continue;
int Tot=siz[x]<siz[u]?siz[x]:(tot-siz[u]);
dp[root=0]=2e9;
f_root(x,u,Tot);dfa[root]=u;
rebuild(root,Tot);
}
}//建立虚树.
int rt1[N],rt2[N];
struct xds{
int lc[N<<3],rc[N<<3],sum[N<<3],size;//存这个节点的左儿子,右儿子,以及区间的和,然后就是推动的下标.
void update(int &u,int pos,int k,int l,int r)
{
if(!u) u=++size;
sum[u]+=k;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) update(lc[u],pos,k,l,mid);
else update(rc[u],pos,k,mid+1,r);
}
int query(int u,int L,int R,int l,int r)//在[l,r]查询[L,R].
{
if(L<=l&&r<=R) return sum[u];
else if(L>r||R<l||!u) return 0;
int mid=(l+r)>>1;
return query(lc[u],L,R,l,mid)+query(rc[u],L,R,mid+1,r);
}
void clear() {memset(lc,0,sizeof(lc));memset(rc,0,sizeof(rc));memset(sum,0,sizeof(sum));size=0;}
}t1,t2;//用于单点修改,区间查询.
void update(int u,int Val)
{
int now=u;
while(now)
{
int fa=dfa[now];
t1.update(rt1[now],dis(now,u),Val,0,dsiz[now]);
if(fa) t2.update(rt2[now],dis(fa,u),Val,0,dsiz[fa]);
now=fa;
}
}
inline int query(int u,int k)
{
int res=0;
int now=u,last=0;
while(now)
{
int d=dis(u,now);
if(d>k) {last=now;now=dfa[now];continue;}
res+=t1.query(rt1[now],0,k-d,0,dsiz[now]);
if(last)
{
res-=t2.query(rt2[last],0,k-d,0,dsiz[now]);
}
last=now;now=dfa[now];
}return res;
}
int main()
{
int n,q;
while(scanf("%d%d",&n,&q)!=EOF)
{
t1.clear();t2.clear();
for(int i=1;i<=n;i++)
{
val[i]=read();
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<M;j++)
{
f[i][j]=0;
}
}root=0;
for(int i=0;i<=n;i++)
{
vector<int>().swap(v[i]);
dep[i]=vis[i]=rt1[i]=rt2[i]=0;
dfa[i]=dsiz[i]=0;
}
for(int i=1;i<n;i++)
{
int x,y;
x=read();y=read();
v[x].push_back(y);
v[y].push_back(x);
}dfs(1,0,1);dp[0]=2e9;
f_root(1,0,n);
rebuild(root,n);
for(int i=1;i<=n;i++)
{
update(i,val[i]);
}
while(q--)
{
char op[2];int u,s;
scanf("%s",op);
u=read();s=read();
if(op[0]=='?')
{
printf("%d\n",query(u,s));
}
else
{
update(u,s-val[u]);val[u]=s;
}
}
}
return 0;
}这个代码多交几次就好了...
但是lca可以更加快一点...
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+3e4,M=19;
int val[N],dep[N],f[N][M];
vector<int>v[N];
namespace IO {
template<typename T> void sc(T &x) { //输入
int f = 1; x = 0;
char ch = getchar();
while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();
if(ch == '-') f = -f;
else x = ch ^ 48;
while((ch = getchar()) >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + (ch ^ 48);
x *= f;
}
template<typename T> void _print(T x) {
if(x > 9) _print(x / 10);
putchar((x % 10) ^ 48);
}
template<typename T> void pr(T x) {
if(x < 0) {
x = -x;
putchar('-');
}
_print(x);
}
}
using namespace IO;
int Log[N];
int lca(int a,int b)
{
if(dep[a] < dep[b]) swap(a,b);int k = dep[a] - dep[b];
for(int i = Log[k];~i;i--) if((k >> i) & 1) a = f[a][i];
if(a == b) return a;
for(int i = Log[dep[a]];~i;i--) if(f[a][i] ^ f[b][i])
a = f[a][i],b = f[b][i];return f[a][0];
}
inline int dis(int a,int b)
{
return dep[a]+dep[b]-2*dep[lca(a,b)];
}//求两个点的树上距离.
void dfs(int u,int fa,int D)
{
dep[u]=D;f[u][0]=fa;
for(int i=1;i<M;i++)
{
f[u][i]=f[f[u][i-1]][i-1];
}
for(int i=0;i<(int)v[u].size();i++)
{
int x=v[u][i];
if(x!=fa) dfs(x,u,D+1);
}
}//处理原树的深度.
int siz[N],dp[N],root,vis[N];//每个点的子树大小和某个点子树中最大的子树最小是多少.
void f_root(int u,int fa,int tot)
{
siz[u]=1;dp[u]=0;
for(int i=0;i<(int)v[u].size();i++)
{
int x=v[u][i];
if(x==fa||vis[x]) continue;
f_root(x,u,tot);siz[u]+=siz[x];
dp[u]=max(dp[u],siz[x]);
}dp[u]=max(dp[u],tot-siz[u]);
if(dp[u]<dp[root]) root=u;
}
int dfa[N],dsiz[N];//记录当前u节点在虚树上的父亲节点是哪个.重心包含的虚数大小.
void rebuild(int u,int tot)
{
vis[u]=1;dsiz[u]=tot;
for(int i=0;i<(int)v[u].size();i++)
{
int x=v[u][i];
if(vis[x]) continue;
int Tot=siz[x]<siz[u]?siz[x]:(tot-siz[u]);
dp[root=0]=2e9;
f_root(x,u,Tot);dfa[root]=u;
rebuild(root,Tot);
}
}//建立虚树.
int rt1[N],rt2[N];
struct xds{
int lc[N<<3],rc[N<<3],sum[N<<3],size;//存这个节点的左儿子,右儿子,以及区间的和,然后就是推动的下标.
void update(int &u,int pos,int k,int l,int r)
{
if(!u) u=++size;
sum[u]+=k;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) update(lc[u],pos,k,l,mid);
else update(rc[u],pos,k,mid+1,r);
}
int query(int u,int L,int R,int l,int r)//在[l,r]查询[L,R].
{
if(L<=l&&r<=R) return sum[u];
else if(L>r||R<l||!u) return 0;
int mid=(l+r)>>1;
return query(lc[u],L,R,l,mid)+query(rc[u],L,R,mid+1,r);
}
void clear() {memset(lc,0,sizeof(lc));memset(rc,0,sizeof(rc));memset(sum,0,sizeof(sum));size=0;}
}t1,t2;//用于单点修改,区间查询.
void update(int u,int Val)
{
int now=u;
while(now)
{
int fa=dfa[now];
t1.update(rt1[now],dis(now,u),Val,0,dsiz[now]);
if(fa) t2.update(rt2[now],dis(fa,u),Val,0,dsiz[fa]);
now=fa;
}
}
inline int query(int u,int k)
{
int res=0;
int now=u,last=0;
while(now)
{
int d=dis(u,now);
if(d>k) {last=now;now=dfa[now];continue;}
res+=t1.query(rt1[now],0,k-d,0,dsiz[now]);
if(last)
{
res-=t2.query(rt2[last],0,k-d,0,dsiz[now]);
}
last=now;now=dfa[now];
}return res;
}
int main()
{
int n,q;
while(scanf("%d%d",&n,&q)!=EOF)
{
t1.clear();t2.clear();
for(int i=1;i<=n;i++)
{
sc(val[i]);
}
for(int i = 2;i <= n;i++) Log[i] = Log[i >> 1] + 1;
for(int i=0;i<=n;i++)
{
for(int j=0;j<M;j++)
{
f[i][j]=0;
}
}root=0;
for(int i=0;i<=n;i++)
{
vector<int>().swap(v[i]);
dep[i]=vis[i]=rt1[i]=rt2[i]=0;
dfa[i]=dsiz[i]=0;
}
for(int i=1;i<n;i++)
{
int x,y;
sc(x);sc(y);
v[x].push_back(y);
v[y].push_back(x);
}dfs(1,0,1);dp[0]=2e9;
f_root(1,0,n);
rebuild(root,n);
for(int i=1;i<=n;i++)
{
update(i,val[i]);
}
while(q--)
{
char op[2];int u,s;
scanf("%s",op);
sc(u);sc(s);
if(op[0]=='?')
{
pr(query(u,s));
puts("");
}
else
{
update(u,s-val[u]);val[u]=s;
}
}
}
return 0;
}
就不用多交了..
京公网安备 11010502036488号