如何免费发布个人网站,网站项目需求分析,搭建网站服务器需要什么配置,旅游网站建设标书题意#xff1a;nnn个点带边权的树#xff0c;动态修改点权viv_ivi#xff0c;最小化 钦定一个点xxx 后 ∑idist(x,i)∗vi\sum\limits_{i} dist(x,i)*v_ii∑dist(x,i)∗vi的值。 n,q≤105n,q \leq10^5n,q≤105#xff0c;度数不超过202020
限制度数的树上的一些诡异…题意nnn个点带边权的树动态修改点权viv_ivi最小化 钦定一个点xxx 后 ∑idist(x,i)∗vi\sum\limits_{i} dist(x,i)*v_ii∑dist(x,i)∗vi的值。
n,q≤105n,q \leq10^5n,q≤105度数不超过202020
限制度数的树上的一些诡异的操作时限很长多半是点分树。
也叫动态点分治但实际上并不是动态的点分治并且有一定误导性所以以后都叫点分树。
点分树是对一个树点分治后的结构建出的树即在点分治时将下一层的重心的父亲设为当前的分治中心。
它具有以下常用的性质
原树与点分树 一个相同的点uuu的儿子vvv为根的子树 一一对应。点分树上两个点的lcalcalca 在原树上这两个点的路径上。树高O(logn)O(\log n)O(logn)
本质上是对树建出的线段树。
在本题中详细讲解。
首先本题实际上求的是带权重心
有个结论
设当前点是uuu,如果vvv比uuu更优
那么有
len(u,v)∗(n−sumv−sumv)0len(u,v)*(n-sum_v-sum_v)0len(u,v)∗(n−sumv−sumv)0
其中sumsumsum表示子树点权和
即
2sumvn2sum_vn2sumvn
然后继续往下走
不难看出对于一个uuu这样的vvv最多只有111个所以答案一定在满足条件的vvv的子树内。如果没有这样的vvv说明uuu是带权重心。
这样是O(n)O(n)O(n)的考虑搬到点分树上
从点分树的根开始往下走
设当前在uuu,我们找到点分树上uuu的一个儿子vvv
注意之前的结论只能往原树上相邻的点走所以你不能直接用这个结论判断vvv
但是如果我们设uuu往 vvv在点分树上的子树 的这个方向走一步 到达的点是www
即 红色为点分树
因为www在原树上的子树 等于 vvv在点分树上的子树
我们想判断答案是否在 vvv在点分树上的子树内可以转换为是否在 www在原树上的子树内
然而如果你判2∗sumvsumrt2*sum_vsum_{rt}2∗sumvsumrt,会发现你还是WA了
原因是你钦定uuu为根之后这棵树的形态已经确定了
你在点分树上一直往下走实际上原树上仍然在乱跳
人话只有第一层的www原树和vvv点分树的子树一样后面的点分树上的子树在原树上甚至可能不是子树。
但是上面已经证明过最多只有一个vvv
我们可以直接算出uuu在原树上的每个儿子的答案和根结点比较如果有一个www比根结点优因为只有一个说明答案在 www在原树上的子树或vvv在点分树上的子树内。
然后想象把这条边断开化归到从vvv开始的子问题。
也就是说uuu和vvv并没有实质关联只是从重心开始方便处理而已。
现在考虑如何计算一个点的答案
维护ansuans_uansu表示以faufa_ufau为根时uuu在点分树上的子树中的点到faufa_ufau的帯权距离距离*点权之和fafafa为在点分树上的父结点。
询问点xxx的答案时先加入点分树上子结点的所有ansansans,然后在点分树上往上跳把兄弟结点的子树中的所有点权挪到父亲上再一起挪到xxx。因为树高O(logn)O(\log n)O(logn)可以保证复杂度。详见代码。
修改的时候暴力跳父亲修改sumsumsum和ansansans就可以了。
#include iostream
#include cstdio
#include cstring
#include cctype
#include vector
#include cassert
#define MAXN 100005
#define MAXM 200005
using namespace std;
typedef long long ll;
inline int read()
{int ans0,f1;char cgetchar();while (!isdigit(c)) (c-)(f-1),cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return f*ans;
}
struct edge{int u,v,w;}e[MAXM];
int head[MAXN],nxt[MAXM],cnt;
void addnode(int u,int v,int w)
{e[cnt](edge){u,v,w};nxt[cnt]head[u];head[u]cnt;
}
int dis[MAXN],pos[MAXN],dfn[MAXM],up[MAXN],tim;
void dfs(int u)
{dfn[pos[u]tim]u;for (int ihead[u];i;inxt[i])if (!pos[e[i].v]){dis[e[i].v]dis[u]e[i].w;up[e[i].v]u;dfs(e[i].v);dfn[tim]u;}
}
int LOG[MAXM],st[20][MAXM];
inline int Min(const int x,const int y){return pos[x]pos[y]? x:y;}
inline void init()
{LOG[0]-1;for (int i1;iMAXM;i) LOG[i]LOG[i1]1;for (int i1;itim;i) st[0][i]dfn[i];for (int i1;i20;i)for (int j1;j(1(i-1))tim;j)st[i][j]Min(st[i-1][j],st[i-1][j(1(i-1))]);
}
inline int lca(const int x,const int y)
{int lpos[x],rpos[y];if (lr) swap(l,r);int tLOG[r-l1];return Min(st[t][l],st[t][r-(1t)1]);
}
inline int dist(const int x,const int y){return dis[x]dis[y]-2*dis[lca(x,y)];}
int rt;
int siz[MAXN],maxp[MAXN]{0x7fffffff};
bool cut[MAXN];
void findrt(int u,int f,int sum)
{siz[u]1,maxp[u]0;for (int ihead[u];i;inxt[i])if (e[i].v!f!cut[e[i].v]){findrt(e[i].v,u,sum);siz[u]siz[e[i].v],maxp[u]max(maxp[u],siz[e[i].v]);}if (sum-siz[u]maxp[u]) maxp[u]sum-siz[u];if (maxp[u]maxp[rt]) rtu;
}
int getsiz(int u,int f)
{int ans1;for (int ihead[u];i;inxt[i])if (e[i].v!f!cut[e[i].v])ansgetsiz(e[i].v,u);return ans;
}
int d[MAXN],sum[MAXN];
ll ans[MAXN];
int fa[MAXN];
vectorint son[MAXN],top[MAXN];
void build()
{int urt;cut[u]true;for (int ihead[u];i;inxt[i])if (!cut[e[i].v]){rt0;findrt(e[i].v,0,getsiz(e[i].v,0));son[u].push_back(rt),top[u].push_back(e[i].v),fa[rt]u;build();}
}
bool vis[MAXN];
void DFS(int u)
{assert(!vis[u]);vis[u]true;for (int i0;i(int)son[u].size();i)DFS(son[u][i]);
}
inline void modify(int x,int v)
{int ux;for (;fa[x];xfa[x]) sum[x]v,ans[x](ll)dist(fa[x],u)*v;sum[x]v;
}
inline ll calc(int x)
{ll res0;for (int i0;i(int)son[x].size();i)resans[son[x][i]];for (int ufa[x],vx;u;vu,ufa[u]){int totd[u];for (int i0;i(int)son[u].size();i)if (son[u][i]!v)resans[son[u][i]],totsum[son[u][i]];res(ll)tot*dist(u,x); }return res;
}
inline ll query(int x)
{ll vcalc(x);for (int i0;i(int)son[x].size();i)if (calc(top[x][i])v)return query(son[x][i]);return v;
}
int main()
{int n,q;nread(),qread();for (int i1;in;i){int u,v,w;uread(),vread(),wread();addnode(u,v,w),addnode(v,u,w);}dfs(1);init();int Rt;findrt(1,0,n),Rtrt,build();while (q--){int x,v;xread(),vread();d[x]v,modify(x,v);printf(%lld\n,query(Rt));}return 0;
}
