正題

題目鏈接:https://www.luogu.com.cn/problem/P3345

---

題目大意

$n$個點的一棵樹，每次修改一個點的點權后詢問一個$x$最小化$$\sum _{y=1}^{n}dis(x,y)?d_y$$

---

解題思路

先是構建一個點分樹，然后考慮如何計算答案。

我們定義一個$f{r}_x$表示點分樹上$f{a}_x$到$x$所在子樹的路徑上第一個節點，我們可以比較$f{r}_x$的答案和$f{a}_x$的答案，如果$f{r}_x$更大，那么就向$x$移動。那么如何計算兩個節點的答案的，我們需要維護三個值$s{d}_x,s{x}_x,s{f}_x$分別表示（下面的子樹都是點分子樹）$x$子樹內的點權和，$x$子樹內的${\sum }_{y=1}^{n}dis(x,y)?d_y$，$x$子樹內的所有點${\sum }_{y=1}^{n}dis(f{a}_x,y)?d_y$。

這樣我們就可以通過枚舉到根節點的路徑計算每個點的答案，時間復雜度$O(n{\log }^{3}n)$（因為有$LCA$求路徑長度）。

考慮優化，我們可以用$RMQ$求$LCA$，每次到一個點時序列中加入這個點，然后回退時加入父節點，之后詢問一個區間中深度最小的節點即可。

時間復雜度$O(n{\log }^{2}n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<stack> #define mp(x,y) make_pair(x,y) #define ll long long using namespace std; const int N=2e5+10,T=22; struct node{int to,next,w; }a[N*2]; int n,m,tot,cnt,ls[N],dep[N],dis[N],f[N][T],lg[N],dfn[N],rfn[N]; int num,root,f0[N],siz[N],fa[N],sd[N],fr[N];ll sw[N],sx[N]; bool v[N];vector<int> e[N];stack<int> s; //struct heap{ // priority_queue<pair<int,int> > q1,q2; // void push(pair<int,int> x) // {q1.push(x);return;} // void pop(pair<int,int> x) // {q2.push(x);return;} // pair<int,int> top(){ // while(!q2.empty()&&q1.top()==q2.top()) // q1.pop(),q2.pop(); // return q1.top(); // } // int size(){return q1.size()-q2.size();} //}q[N]; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;return; } void dfs(int x,int fa){dfn[++cnt]=x;rfn[x]=cnt;dep[x]=dep[fa]+1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;dis[y]=dis[x]+a[i].w;dfs(y,x);dfn[++cnt]=x;}return; } void init(){dfs(1,1);for(int i=1;i<=cnt;i++)f[i][0]=dfn[i];for(int i=2;i<=cnt;i++)lg[i]=lg[i/2]+1;for(int j=1;(1<<j)<=cnt;j++)for(int i=1;i+(1<<j)-1<=cnt;i++){int x=f[i][j-1],y=f[i+(1<<j-1)][j-1];f[i][j]=dep[x]<dep[y]?x:y;}return; } int LCA(int x,int y){int l=rfn[x],r=rfn[y];if(l>r)swap(l,r);int z=lg[r-l+1];x=f[l][z];y=f[r-(1<<z)+1][z];return dep[x]<dep[y]?x:y; } int get_dis(int x,int y) {return dis[x]+dis[y]-2*dis[LCA(x,y)];} void groot(int x,int fa){siz[x]=1;f0[x]=0;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa||v[y])continue;groot(y,x);siz[x]+=siz[y];f0[x]=max(f0[x],siz[y]);}f0[x]=max(f0[x],num-siz[x]);if(f0[x]<f0[root])root=x;return; } void build(int x){v[x]=1;int S=num;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(v[y])continue;num=(siz[y]>siz[x])?(S-siz[x]):(siz[y]);root=0;groot(y,x);fr[root]=y;y=root;build(y);fa[y]=x;e[x].push_back(y);}return; } ll count(int x){ll ans=sx[x];for(int y=x;fa[y];y=fa[y])ans+=1ll*(sd[fa[y]]-sd[y])*get_dis(x,fa[y])+sx[fa[y]]-sw[y];return ans; } int main() {freopen("tree1.in","r",stdin);scanf("%d%d",&n,&m);for(int i=1;i<n;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);addl(x,y,w);addl(y,x,w);}init();num=n;f0[0]=n;groot(1,1);int pr=root;build(root);while(m--){int x,w,y;scanf("%d%d",&x,&w);y=x;while(x){ll z=1ll*w*get_dis(y,fa[x]?fa[x]:x);sw[x]+=z;sx[fa[x]]+=z;sd[x]+=w;x=fa[x];}x=pr;ll ans=count(x);while(1){if(e[x].empty())break;ll z=0;bool flag=0;ans=count(x);for(int i=0;i<e[x].size();i++)if((z=count(fr[e[x][i]]))<ans){x=e[x][i];flag=1;break;}if(flag)continue;break;}ans=count(x);printf("%lld\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的P3345-[ZJOI2015]幻想乡战略游戏【点分树,RMQ】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。