昆明网站设计制造,wordpress如何添加自定义链接,网站生成海报功能怎么做的,wordpress打开高级设置CF856D Masha and Cactus 我们先捞出一个根节点#xff0c;那么一次旋变就是对路径上点的覆盖。 设 \(dp_{i,0}\) 表示 \(i\) 没有选择时子树内最大收益#xff0c;\(dp_{i,1}\) 表示 \(i\) 选择时子树内最大收益#xff0c;那么将每条边存在 \(lca\) 上。 之后贡献怎么算那么一次旋变就是对路径上点的覆盖。 设 \(dp_{i,0}\) 表示 \(i\) 没有选择时子树内最大收益\(dp_{i,1}\) 表示 \(i\) 选择时子树内最大收益那么将每条边存在 \(lca\) 上。 之后贡献怎么算我们需要快速计算不在根到子树内一点路径上但与路径上的点直接相连的子树内点的权值之和。这里有个计算技巧 \(\color{yellow}{\bigstar\texttt{Trick}}\)设 \(g_i-val_i\sum_{j\in son_{i}}val_{j}\)那么上面的答案就是路径所有 \(g_i\) 之和加上根节点权值。 查询路径可以转化为子树加、单点查询树状数组解决即可。 #define Maxn 400005
#define Maxlogn 22
int n,m,tot,Time;
int hea[Maxn],nex[Maxn1],ver[Maxn1];
int dfnl[Maxn],dfnr[Maxn],dep[Maxn],fa[Maxlogn][Maxn];
ll f[Maxn],g[Maxn];
struct EDGE
{int u,v,val;EDGE(int U0,int V0,int Val0):u(U),v(V),val(Val){}
};
vectorEDGE e[Maxn];
inline void add(int x,int y){ ver[tot]y,nex[tot]hea[x],hea[x]tot; }
struct BIT
{ll tree[Maxn];inline void add(int x,ll k){ while(xn) tree[x]k,xx(-x); }inline ll query(int x){ ll ret0; while(x) rettree[x],x-x(-x); return ret; }
}T;
inline int lca(int x,int y)
{if(dep[x]dep[y]) swap(x,y);for(int i20;i0;i--) if(dep[fa[i][y]]dep[x]) yfa[i][y];if(xy) return x;for(int i20;i0;i--) if(fa[i][x]!fa[i][y]) xfa[i][x],yfa[i][y];return fa[0][x];
}
inline void addpath(int x,ll val) { T.add(dfnl[x],val),T.add(dfnr[x]1,-val); }
inline ll querypath(int x) { return T.query(dfnl[x]); }
void dfs1(int x)
{dfnl[x]Time;for(int ihea[x];i;inex[i]){fa[0][ver[i]]x,dep[ver[i]]dep[x]1;for(int j1;j20;j) fa[j][ver[i]]fa[j-1][fa[j-1][ver[i]]];dfs1(ver[i]);}dfnr[x]Time;
}
void dfs2(int x)
{ll sum0;for(int ihea[x];i;inex[i]) dfs2(ver[i]),sumf[ver[i]];for(EDGE v:e[x]){ll tmpquerypath(v.u)querypath(v.v)sumv.val;f[x]max(f[x],tmp);}f[x]max(f[x],sum),g[x]sum-f[x],addpath(x,g[x]);
}
int main()
{nrd(),mrd();for(int i2,x;in;i) xrd(),add(x,i);dep[1]1,dfs1(1);for(int i1,u,v,val,LCA;im;i)urd(),vrd(),valrd(),LCAlca(u,v),e[LCA].eb(u,v,val);dfs2(1);printf(%lld\n,f[1]);return 0;
}
