[luogu3676]小清新数据结构题

前言

此题貌似有不少做法

题目相关

链接

题目大意

给出一棵无根树，支持两个操作
1.修改一个点的权值
2.指定一个点，计算以其为根时每个子树权值平方和

数据范围

$n,q\le 200000$

题解

对于这题，我们发现直接维护好像不太方便
考虑转化一下问题
设S=∑i=1nsiS=\sum_{i=1}^ns_iS=∑i=1n​si​
我们考虑一个值∑i=1n∑j=1nsisjdis(i,j)\sum_{i=1}^n\sum_{j=1}^n s_is_jdis(i,j)∑i=1n​∑j=1n​si​sj​dis(i,j)，我们设其为$T$，我们发现只要不修改点权，那么$T$就是不变的
考虑将$T$换个形式，我们设以某个点为根，$i$号点的子树权值和是viv_ivi​
发现12T=∑i=1nvi(S−vi)\frac12T=\sum_{i=1}^nv_i(S-v_i)21​T=∑i=1n​vi​(S−vi​)（我们发现等式右边相当于是枚举一个点，这个点的子树内的点到子树外的点贡献一个乘积，这样的话一个点对会贡献路径长度次答案）
即对于任何一个点为根，等式都成立
我们发现$T$的值可以直接用动态点分治维护（查询所有点到一个点的距离乘权值的和，具体做法可以看幻想乡战略游戏博客）即可，复杂度大概是$\mathcal{O}(nlogn)$的
我们把$T$的式子展开，我们发现
12T=∑i=1nviS−vi2=S∑i=1nvi−∑i=1nvi2\begin{aligned} \frac12T&=\sum_{i=1}^nv_iS-v_i^2 &=S\sum_{i=1}^nv_i-\sum_{i=1}^nv_i^2 \end{aligned}21​T​=i=1∑n​vi​S−vi2​​=Si=1∑n​vi​−i=1∑n​vi2​​
即∑i=1nvi2=S∑i=1nvi−12T\sum_{i=1}^nv_i^2=S\sum_{i=1}^nv_i-\frac12Ti=1∑n​vi2​=Si=1∑n​vi​−21​T
容易发现$S$很好维护，现在只要再维护∑i=1nvi\sum_{i=1}^nv_i∑i=1n​vi​即可
我们发现这玩意儿也很好弄
∑i=1nvi=∑i=1nsidis(root,i)+∑i=1nsi\sum_{i=1}^nv_i=\sum_{i=1}^ns_idis(root,i)+\sum_{i=1}^ns_ii=1∑n​vi​=i=1∑n​si​dis(root,i)+i=1∑n​si​
这玩意儿动态点分治里已经维护好了
方便起见，我这里贴一个最终的式子
∑i=1nvi2=S(∑i=1nsidis(root,i)+∑i=1nsi)−12(∑i=1n∑j=1nsisjdis(i,j))=S∑i=1nsidis(root,i)+S2−12∑i=1n∑j=1nsisjdis(i,j)=S∑i=1nsidis(root,i)+S2−∑i=1n∑j=i+1nsisjdis(i,j)\begin{aligned} \sum_{i=1}^nv_i^2&=S(\sum_{i=1}^ns_idis(root,i)+\sum_{i=1}^ns_i)-\frac12(\sum_{i=1}^n\sum_{j=1}^n s_is_jdis(i,j))\\ &=S\sum_{i=1}^ns_idis(root,i)+S^2-\frac12\sum_{i=1}^n\sum_{j=1}^n s_is_jdis(i,j)\\ &=S\sum_{i=1}^ns_idis(root,i)+S^2-\sum_{i=1}^n\sum_{j=i+1}^n s_is_jdis(i,j) \end{aligned}i=1∑n​vi2​​=S(i=1∑n​si​dis(root,i)+i=1∑n​si​)−21​(i=1∑n​j=1∑n​si​sj​dis(i,j))=Si=1∑n​si​dis(root,i)+S2−21​i=1∑n​j=1∑n​si​sj​dis(i,j)=Si=1∑n​si​dis(root,i)+S2−i=1∑n​j=i+1∑n​si​sj​dis(i,j)​
总复杂度$\mathcal{O}(nlogn)$

代码

#include
#include
#include
#include
namespace fast_IO
{const int IN_LEN=1000000,OUT_LEN=1000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
#define rg register
typedef long long ll;
template <typename T> inline T max(const T a,const T b){return a>b?a:b;}
template <typename T> inline T min(const T a,const T b){return a<b?a:b;}
template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;}
template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;}
template <typename T> inline T abs(const T a){return a>0?a:-a;}
template <typename T> inline void Swap(T&a,T&b){T c=a;a=b;b=c;}
template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);}
template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;}
template <typename T> inline T square(const T x){return x*x;};
template <typename T> inline void read(T&x)
{char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;
}
template <typename T> inline void printe(const T x)
{if(x>=10)printe(x/10);putchar(x%10+'0');
}
template <typename T> inline void print(const T x)
{if(x<0)putchar('-'),printe(-x);else printe(x);
}
const int maxn=200001,maxm=400001;
int n,Q;
int head[maxn],nxt[maxm],tow[maxm],tmp;
inline void addb(const int u,const int v)
{tmp++;nxt[tmp]=head[u];head[u]=tmp;tow[tmp]=v;
}
ll SIZE;
int minn,root,son[maxn];
bool vis[maxn];
void getroot(const int u,const int fa)
{son[u]=1;int maxx=0;for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v!=fa&&!vis[v]){getroot(v,u);son[u]+=son[v];maxd(maxx,son[v]);}}maxd(maxx,(int)SIZE-son[u]);if(maxx<minn)minn=maxx,root=u;
}
int ROOT,F[maxn];
std::vector<int>E[maxn];
int fr[maxn];
void solve(const int u,const int SZ,const int SON)
{vis[u]=1;for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(!vis[v]){minn=0x7fffffff,SIZE=son[v];if(SIZE>SON)SIZE=SZ-SON;getroot(v,u);E[u].push_back(root);F[root]=u,fr[root]=v;solve(root,SIZE,son[root]);}}
}
int rmq[maxm][21],top,fst[maxn];
ll dep[maxn];
void dfs(const int u,const int fa)
{rmq[++top][0]=u;fst[u]=top;for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v!=fa)dep[v]=dep[u]+1,dfs(v,u),rmq[++top][0]=u;}
}
int bit[21],log_[3000000];
int MIN(const int u,const int v){return dep[u]<dep[v]?u:v;}
int lca(const int u,const int v)
{const int A=min(fst[u],fst[v]),B=max(fst[u],fst[v]);return MIN(rmq[A][log_[B-A+1]],rmq[B-bit[log_[B-A+1]]+1][log_[B-A+1]]);
}
ll dis(const int u,const int v)
{return dep[u]+dep[v]-(dep[lca(u,v)]<<1);
}
ll g[maxn],f[maxn],size[maxn];
ll vvv[maxn],T;
int stack[21],tot;ll sz[233];
ll calc(const int l,const int r)
{ll res=0;for(rg int i=1;i<=tot;i++)if(dis(stack[i],l)>dis(stack[i],r))res+=sz[i];return res;
}
ll Res(const int p)
{ll res=g[p];stack[++tot]=p;for(rg int i=1;i<tot;i++)res+=g[stack[i]]-f[stack[i+1]]+(size[stack[i]]-size[stack[i+1]])*dis(stack[i],p);return res;
}
ll qz(const int p)
{tot=1;int gg=p;while(gg!=ROOT)gg=F[gg],tot++;for(rg int i=tot,j=p;i>=1;i--,j=F[j])stack[i]=j;for(rg int i=1;i<tot;i++)sz[i]=size[stack[i]]-size[stack[i+1]];tot--;return Res(p);
}
inline void add(int p,const int more)
{const int O=p;vvv[p]+=more,size[p]+=more,SIZE+=more;while(p!=ROOT){const ll R=dis(O,F[p]);f[p]+=R*more,g[F[p]]+=R*more;p=F[p];size[p]+=more;}T+=more*qz(O);
}
int main()
{bit[0]=1;for(rg int i=1;i<=20;i++)bit[i]=bit[i-1]<<1;for(rg int i=1;i<=20;i++)for(rg int j=bit[i];j<(bit[i]<<1);j++)log_[j]=i;read(n),read(Q);for(rg int i=1;i<n;i++){int u,v;read(u),read(v);addb(u,v),addb(v,u);}minn=0x7fffffff,SIZE=n,getroot(1,1);ROOT=root;solve(root,SIZE,son[root]);dfs(1,1);for(rg int i=1;i<=20;i++)for(rg int j=1;j+bit[i]-1<=top;j++)rmq[j][i]=MIN(rmq[j][i-1],rmq[j+bit[i-1]][i-1]);SIZE=0;for(rg int i=1;i<=n;i++){int x;read(x);add(i,x);}for(rg int i=1;i<=Q;i++){int opt,x,y;read(opt);if(opt==1)read(x),read(y),y-=vvv[x],add(x,y);else read(x),print(SIZE*qz(x)-T+SIZE*SIZE),putchar('\n');}return flush(),0;
}

总结

和幻想乡那题差不多，还是挺清真的

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！