[zjoi2015]幻想乡战略游戏

前言

略略略

题目相关

链接

题目大意

给出一棵树，每次修改一个点的权值，维护一个带权重心
啥是带权重心？
设点$i$的值为$V_i$我们要选一个点$u$，每个点对应一个值：
$$\sum _{v=1}^n{V}_v\ast dis(u,v)$$
我们要选一个$u$使得这个值最小
输出最小的值

数据范围

$n,q\le 10^5$，每个点的度数不多于20，时限6s

题解

动态点分治（点分树）
很久之前学了点分树，但一直都没做什么题
我们考虑这样一件事
假如我们现在选了一个点$u$，那么只有它向带权重心的方向$v$移动时答案才会变优（证明很显然，带权重心方向的点权和比另外一边的点权大，这样的话e*点权只差就是正的）
我们考虑最裸的情况，每次修改后，我们从根节点开始，如果其往某个子树移动答案会变优（设$siz{e}_i$为$i$的子树大小，那么这个条件是$e_{u,v}\ast （siz{e}_u-siz{e}_v-siz{e}_v<0$，容易发现这样的儿子对多只有一个），那么说明带权重心在那个子树中，那就把当前答案往那个子树移
我们发现这个复杂度可以被卡到$\mathcal{O}(n^2)$，因为往儿子走可能会走很多次

考虑点分治之后建出点分树，我们在跳子树的时候跳到那个子树的重心（注意与带权重心区分）即可，容易发现，由于点分树树高logn，所以这个跳子树的操作使得复杂度变为$\mathcal{O}(nlogn)$

现在要快速维护每个点的答案（当然是推过来而不是直接求）
我们维护每个分治子树权值和$siz{e}_u$（$u$为分治重心），每个分治子树到重心的贡献值$g_u$，每个节点子树到该子树的lca的父亲的贡献值$f_u$
怎么维护呢？即对于一次修改怎么维护答案
我们发现，直接跳点分树即可，用$\mathcal{O}(1)$求距离的话，单次修改的复杂度是$\mathcal{O}(logn)$的
再维护一个全局点权和$SIZE$
我们现在相当于对于当前答案的每条出边，并且询问这条边划分出的子树$size$是否大于全局的一半，如果是就走过去，直到找到答案点，最终计算答案
我们发现子树size和答案并不好维护
考虑记录历史走过的每一个点分重心，这样我们可以做到单次$logn$的询问
我们发现一个点的度数总共只有$20$个，直接枚举出边即可

综上，复杂度$\mathcal{O}(20nlo{g}^{2}n)$
不是很满，但是复杂度感觉挺高的

代码

#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=100001,maxm=200001; int n,Q; int head[maxn],nxt[maxm],tow[maxm],vau[maxm],tmp; inline void addb(const int u,const int v,const int w) {tmp++;nxt[tmp]=head[u];head[u]=tmp;tow[tmp]=v;vau[tmp]=w; } int minn,root,SIZE,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,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]+vau[i],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]; int stack[21],tot;ll sz[21]; 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; } 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,w;read(u),read(v),read(w);addb(u,v,w),addb(v,u,w);}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<=Q;i++){int p,O,more;read(p),O=p,read(more),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;}p=ROOT;tot=0;while(1){bool fla=1;for(unsigned int j=0;j<E[p].size();j++){const int v=E[p][j];const ll SZ=calc(p,fr[v])+size[v];if(SZ*2>SIZE){fla=0;stack[++tot]=p,sz[tot]=size[p]-size[v];p=v;break;}}if(fla)break;}print(Res(p)),putchar('\n');}return flush(),0; }

总结

对点分树的理解程度++
感觉自己还是做题太少了

总结

以上是生活随笔为你收集整理的[zjoi2015]幻想乡战略游戏的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。