建设网站的企业邮箱,企业信用中国官网查询,教做布艺的网站,软件界面设计用什么软件Portal -- bzoj4712 Description 给你一棵树#xff0c;节点从\(1\)到\(n\)编号#xff0c;每个节点有一个权值#xff0c;有若干次操作#xff0c;操作有以下两种#xff1a; \((C,x,delta)\)#xff1a;将编号为\(x\)的点的权值改为\(delta\) \((Q,x)\)#xff1a…Portal -- bzoj4712 Description 给你一棵树节点从\(1\)到\(n\)编号每个节点有一个权值有若干次操作操作有以下两种 \((C,x,delta)\)将编号为\(x\)的点的权值改为\(delta\) \((Q,x)\)询问将\(x\)号节点为根的子树中的所有叶子结点与子树外的其他所有叶子节点分离的最小代价分离可以通过删除节点实现删除一个节点的对应代价为该点的权值 数据范围\(n200000\)任意\(delta\)均为非负数答案在long long范围内 Solution 这题貌似是。。经典的动态dp问题维护重链信息\(f\)和轻儿子信息之和\(g\)之后可以用树剖解决 我们先考虑没有修改操作的情况那就是直接dp 记\(f[x]\)表示以\(x\)为根的子树的答案\(val[x]\)表示\(x\)点的权值那么有\[ f[x]min(val[x],\sum\limits_{x\rightarrow u}f[u]) \] 如果要修改的话我们考虑树剖再定义一个数组\(g\)\(g[x]\)表示\(x\)的轻儿子的\(f\)值之和那么就有\[ f[x]min(val[x],f[son[x]]g[x]) \] 其中\(son[x]\)表示的是\(x\)的重儿子 这个时候就有好几种不同的做法了反正就是维护这两个值就好了接下来讲的是一种通过维护一个类似转移矩阵一样的东西来用树剖维护的方法 我们考虑定义一种新的矩阵乘法额好像也不能叫做矩阵乘法反正就是一种新的运算\[ C[i][j]min(A[i][k]B[k][j]) \] 其中\(A,B,C\)都是矩阵其实这种运算就是将原来的矩阵乘法的乘法改成了取最小值 这个运算是满足结合律的具体证明的话就是我们可以将一次这样的运算理解成求最短路然后连续两次这样的运算的话就是相当于你有三排点要求最左边到最右边的最短路显然你可以先求出左边两排的最短路或者先求出右边两排的最短路最后得到的结果是一样的 定义完这样的运算有什么用呢我们可以考虑将\(f[x]\)的求值过程用这种运算来实现为了方便表示我们将这种运算的符号约定为\(*\)\[ \begin{bmatrix}f[x]\\0\end{bmatrix}\begin{bmatrix}g[x]val[x]\\00\end{bmatrix}*\begin{bmatrix}f[son[x]]\\0\end{bmatrix} \] 具体的话就是。。大力展开一下就好了 然后我们可以发现\(\begin{bmatrix}f[son[x]]\\0\end{bmatrix}\)是可以写成\(\begin{bmatrix}g[son[son[x]]]val[son[son[x]]]\\00\end{bmatrix}\)的一路写下去就会发现其实就是\(x\)所在的整条重链中从\(x\)这个位置的矩阵一路连续运算一直到重链底就好了 注意到这个剖完之后就是一段连续的区间然后这样我们就可以放心用线段树来维护区间的矩阵的连续运算得到的结果然后其他的就是跟树剖差不多的操作了 其实还是有(hen)点(da)区别的具体一点就是 1、查询 与普通树剖不同的是这样我们维护的是。。某个位置到链底的权值运算和所以。。我们需要记录的是每个点所在的链底在哪里然后查询的时候并不需要往上跳直接查就好了 2、修改 修改的话因为这里会影响到祖先的\(g\)值所以我们还是要常规操作一路跳上去不过不同的是这里修改直接暴力通过线段树区间查询求得\(f[top[x]\)然后在\(g[pre[top[x]]]\)里面减去\(pre[x]\)表示\(x\)在原树上的直接祖先\(top[x]\)表示\(x\)所在的重链头然后更新线段树中的信息然后再将新的值加回\(g[pre[top[x]]]\)中 然后就十分愉悦\(O(nlog^2n)\)做完啦这个做法有一个好处就是。。就算没有保证修改的\(delta\)非负也可以直接做以及重载运算符之后线段树写起来很爽qwq 以及洛谷上面貌似有碾爆LCT和树剖的一个\(log\)做法qwqorzlyy然而。。我太懒了并没有写qwq 代码大概长这个样子 #includeiostream
#includecstdio
#includecstring
#define ll long long
using namespace std;
const int N200010,SEGN*4;
const ll inf1LL60;
struct xxx{int y,nxt;
}a[N*2];
int h[N],lis[N],dfn[N],ed[N],pre[N],sz[N];//edthe end of the chain
ll f[N],g[N],val[N];
int son[N],top[N];
int n,m,tot,dfn_t;
ll ans;
struct Mtrix{/*{{{*/ll a[2][2];int n;void init(int _n){n_n;for (int i0;in;i)for (int j0;jn;j) a[i][j]inf;}friend Mtrix operator * (Mtrix x,Mtrix y){Mtrix ret; ret.nx.n;for (int i0;iret.n;i)for (int j0;jret.n;j){ret.a[i][j]inf;for (int k0;kret.n;k)if (x.a[i][k]!infy.a[k][j]!inf)ret.a[i][j]min(ret.a[i][j],x.a[i][k]y.a[k][j]);}return ret;}
};/*}}}*/
namespace Seg{/*{{{*/int ch[SEG][2];Mtrix info[SEG];int n,tot;void pushup(int x){info[x]info[ch[x][0]]*info[ch[x][1]];}void _build(int x,int l,int r){info[x].init(2);if (lr){info[x].a[0][0]g[lis[l]];info[x].a[0][1]val[lis[l]];info[x].a[1][0]info[x].a[1][1]0;return;}int midlr1;ch[x][0]tot; _build(ch[x][0],l,mid);ch[x][1]tot; _build(ch[x][1],mid1,r);pushup(x);}void build(int _n){n_n;tot1;_build(1,1,n);}void _update(int x,int d,int lx,int rx){if (lxrx){info[x].a[0][0]g[lis[lx]];info[x].a[0][1]val[lis[lx]];info[x].a[1][0]info[x].a[1][1]0;return;}int midlxrx1;if (dmid) _update(ch[x][0],d,lx,mid);else _update(ch[x][1],d,mid1,rx);pushup(x);}void update(int d){_update(1,d,1,n);}Mtrix _query(int x,int l,int r,int lx,int rx){if (llxrxr) return info[x];int midlxrx1;if (rmid) return _query(ch[x][0],l,r,lx,mid);else if (lmid) return _query(ch[x][1],l,r,mid1,rx);else{return _query(ch[x][0],l,mid,lx,mid)*_query(ch[x][1],mid1,r,mid1,rx);}}Mtrix query(int l,int r){return _query(1,l,r,1,n);}
}/*}}}*/
void add(int x,int y){a[tot].yy; a[tot].nxth[x]; h[x]tot;}
void dfs(int fa,int x){int u;sz[x]1; son[x]0; pre[x]fa;for (int ih[x];i!-1;ia[i].nxt){ua[i].y;if (ufa) continue;dfs(x,u);sz[x]sz[u];if (sz[u]sz[son[x]]) son[x]u;}
}
void dfs1(int fa,int x){int u,cntson0;dfn[x]ed[x]dfn_t; lis[dfn_t]x;if (son[x]){top[son[x]]top[x];dfs1(x,son[x]);ed[x]ed[son[x]];f[x]f[son[x]];cntson;}for (int ih[x];i!-1;ia[i].nxt){ua[i].y;if (ufa||uson[x]) continue;top[u]u;dfs1(x,u);g[x]f[u];cntson;}if (cntson0) g[x]inf,f[x]val[x];elsef[x]min(val[x],f[x]g[x]);
}
ll query(int x){Mtrix tmpSeg::query(dfn[x],ed[x]);return min(tmp.a[0][0],tmp.a[0][1]);
}
void update(int x,int delta){ll tmp;val[x]delta;while (top[x]){tmpquery(top[x]);if (pre[top[x]])g[pre[top[x]]]-tmp;Seg::update(dfn[x]);tmpquery(top[x]);if (pre[top[x]])g[pre[top[x]]]tmp;xpre[top[x]];}
}int main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);
#endifchar op[5];int x,y;scanf(%d,n);for (int i1;in;i) scanf(%lld,vali);memset(h,-1,sizeof(h));tot0;for (int i1;in;i){scanf(%d%d,x,y);add(x,y); add(y,x);}dfs(0,1);top[1]1; dfn_t0;dfs1(0,1);Seg::build(dfn_t);scanf(%d,m);for (int i1;im;i){scanf(%s,op);if (op[0]C){scanf(%d%d,x,y);update(x,y);}else{scanf(%d,x);ansquery(x);printf(%lld\n,ans);}}
} 转载于:https://www.cnblogs.com/yoyoball/p/9513666.html
