前言

此題貌似有不少做法

題目相關(guān)

鏈接

題目大意

給出一棵無根樹，支持兩個(gè)操作
1.修改一個(gè)點(diǎn)的權(quán)值
2.指定一個(gè)點(diǎn)，計(jì)算以其為根時(shí)每個(gè)子樹權(quán)值平方和

數(shù)據(jù)范圍

$n,q\le 200000$

題解

對于這題，我們發(fā)現(xiàn)直接維護(hù)好像不太方便
考慮轉(zhuǎn)化一下問題
設(shè)$S={\sum }_{i=1}^n{s}_i$
我們考慮一個(gè)值${\sum }_{i=1}^n{\sum }_{j=1}^n{s}_i{s}_{j}dis(i,j)$，我們設(shè)其為$T$，我們發(fā)現(xiàn)只要不修改點(diǎn)權(quán)，那么$T$就是不變的
考慮將$T$換個(gè)形式，我們設(shè)以某個(gè)點(diǎn)為根，$i$號點(diǎn)的子樹權(quán)值和是$v_i$
發(fā)現(xiàn)$\frac{1}{2}T={\sum }_{i=1}^n{v}_i(S?v_i)$（我們發(fā)現(xiàn)等式右邊相當(dāng)于是枚舉一個(gè)點(diǎn)，這個(gè)點(diǎn)的子樹內(nèi)的點(diǎn)到子樹外的點(diǎn)貢獻(xiàn)一個(gè)乘積，這樣的話一個(gè)點(diǎn)對會(huì)貢獻(xiàn)路徑長度次答案）
即對于任何一個(gè)點(diǎn)為根，等式都成立
我們發(fā)現(xiàn)$T$的值可以直接用動(dòng)態(tài)點(diǎn)分治維護(hù)（查詢所有點(diǎn)到一個(gè)點(diǎn)的距離乘權(quán)值的和，具體做法可以看幻想鄉(xiāng)戰(zhàn)略游戲博客）即可，復(fù)雜度大概是$\mathcal{O}(nlogn)$的
我們把$T$的式子展開，我們發(fā)現(xiàn)
$$\begin{array}{rlr}\frac{1}{2}T& =\sum _{i=1}^n{v}_{i}S?v_i^2& =S\sum _{i=1}^n{v}_i?\sum _{i=1}^n{v}_i^2\end{array}$$
即$$\sum _{i=1}^n{v}_i^2=S\sum _{i=1}^n{v}_i?\frac{1}{2}T$$
容易發(fā)現(xiàn)$S$很好維護(hù)，現(xiàn)在只要再維護(hù)${\sum }_{i=1}^n{v}_i$即可
我們發(fā)現(xiàn)這玩意兒也很好弄
$$\sum _{i=1}^n{v}_i=\sum _{i=1}^n{s}_{i}dis(root,i)+\sum _{i=1}^n{s}_i$$
這玩意兒動(dòng)態(tài)點(diǎn)分治里已經(jīng)維護(hù)好了
方便起見，我這里貼一個(gè)最終的式子
$$\begin{array}{rl}\sum _{i=1}^n{v}_i^2& =S(\sum _{i=1}^n{s}_{i}dis(root,i)+\sum _{i=1}^n{s}_i)?\frac{1}{2}(\sum _{i=1}^n\sum _{j=1}^n{s}_i{s}_{j}dis(i,j))\\ & =S\sum _{i=1}^n{s}_{i}dis(root,i)+S^2?\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{s}_i{s}_{j}dis(i,j)\\ & =S\sum _{i=1}^n{s}_{i}dis(root,i)+S^2?\sum _{i=1}^n\sum _{j=i+1}^n{s}_i{s}_{j}dis(i,j)\end{array}$$
總復(fù)雜度$\mathcal{O}(nlogn)$

代碼

#include<cstdio> #include<cctype> #include<algorithm> #include<vector> 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; }

總結(jié)

和幻想鄉(xiāng)那題差不多，還是挺清真的

總結(jié)

以上是生活随笔為你收集整理的[luogu3676]小清新数据结构题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。