P3345 [ZJOI2015]幻想乡战略游戏 题解
题面
设 \(sum_u\) 为 \(u\) 子树内 \(d\) 的和，\(sum_d\) 和 \(sum_ch\) 意义是常见点分树容斥，记录子树内 \(d\times dist\) 的和。
首先注意一个性质：假设当前答案为 \(u\)，那么如果 \(u\) 的某个儿子 \(v\) 的答案更优，那么有 \(sum_v
点击查看代码
const int N=1e5+13;
struct Edge{int v,w,nxt;}e[N<<1];
int n,h[N],etot;
inline void add_edge(int u,int v,int w){e[++etot]=(Edge){v,w,h[u]};h[u]=etot;}
namespace Tree{
int fa[N],dep[N],siz[N],son[N],top[N],dis[N];
void dfs1(int u,int f,int deep){
dep[u]=deep,siz[u]=1,fa[u]=f;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==f) continue;
dis[v]=dis[u]+e[i].w;
dfs1(v,u,deep+1);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
}
inline void init(){dfs1(1,0,0);dfs2(1,1);}
inline int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]