P9808 解题报告
Hoks
·
·
题解
前言
美妙树剖，比较套路了吧，反正一眼秒了。
原本不想补题解的，但是做到这题还是我的御用纯情娇羞可爱内向小男娘 Loser_Syx 把这题推给我了捏。
博客内食用更佳。
思路分析
题目这么大个式子摆在眼前肯定先考虑暴力化简下啊。
题目给定的一个函数外面再套求和肯定是不太好做的，所以考虑先拆里面。
里面的直接使用树上距离公式就行了（注意这里的深度是指到根节点的距离）。
dis(x,y)=dep_x+dep_y-2\times dep_{LCA(x,y)}
用这个式子就可以把之前那个又臭又长的式子破开成为：
\sum\limits_{i=1}^k\sum\limits_{j=1}^k dep_{a_i}+dep_{a_j}-2\times dep_{LCA(a_i,a_j)}
然后把这里面好算的东西拿出来破开：
2\times(k-1)\times \sum\limits_{i=1}^kdep_{a_i}-4\times\sum\limits_{i=1}^k\sum\limits_{j=i+1}^kdep_{LCA(a_i,a_j)}
（虽然我感觉很惊讶，但是另一篇题解后面的这个系数好像写错了，应该是 4，原因是把从 1 开始变为从 i+1 开始应该再乘上一个 2 的系数。）
然后把前面一坨和后面那一坨分开，也就是令
然后前面那玩意很好维护了，出新点的时候直接加上这个点即可。
重点则在后面这一块怎么求。
首先思考下这一坨他在树上的意义是什么？
是根到他们 LCA 的距离吗？（那不是说了和说了一样。）
所以考虑为什么我们可以把 $dis(x,y)$ 拆开的原因。
那他的意义即为：$1\rightarrow a_i,1\rightarrow a_j$ 路径相交的长度。
路径相交？那我们便可以在把一个村庄 $i$ 变为新的城堡后把 $1\rightarrow i$ 上的路径的边权全部倍数 $+1$。
查询的时候只要直接询问 $1\rightarrow i$ 上的路径长度求出来加入 $ans2$ 中即可。
具体细节见又臭又长的代码了。
## 代码
```cpp
#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define int long long
using namespace std;
const int N=200010,INF=0x3f3f3f3f3f3f3f3f;
struct edge
{int v,nxt,w;}e[N<<1];
int n,k,tot,cnt,ans1,ans2;
int head[N],top[N],id[N],dfn[N],a[N];
int fa[N],dep[N],son[N],si[N];
int lz[N<<2],s[N<<2],re[N<<2];
static char buf[1000000],*paa=buf,*pd=buf;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline int read(void){
int x(0),a(1);char fc(getchar());
while(!isdigit(fc)){if(fc=='-') a=-1;fc=getchar();}
while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
return x*a;
}
inline void print(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+'0');
}
void add(int u,int v,int w){e[++tot].v=v,e[tot].nxt=head[u],head[u]=tot,e[tot].w=w;}
void dfs1(int u,int ff)
{
fa[u]=ff,si[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==ff) continue;
a[v]=e[i].w;dep[v]=dep[u]+a[v];
dfs1(v,u);si[u]+=si[v];
if(si[v]>si[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topf)
{
top[u]=topf,dfn[u]=++cnt,id[cnt]=a[u];
if(son[u]) dfs2(son[u],topf);
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==son[u]||v==fa[u]) continue;
dfs2(v,v);
}
}
void pushdown(int p){lz[ls]+=lz[p],lz[rs]+=lz[p],re[ls]+=s[ls]*lz[p],re[rs]+=s[rs]*lz[p],lz[p]=0;}
void build(int p,int l,int r)
{
if(l==r) return void(s[p]=id[l]);
build(ls,l,mid),build(rs,mid+1,r);s[p]=s[ls]+s[rs];
}
void modify(int p,int l,int r,int st,int ed)
{
if(l>ed||r<st) return;
if(l>=st&&r<=ed) return void(lz[p]++),void(re[p]+=s[p]);pushdown(p);
modify(ls,l,mid,st,ed);modify(rs,mid+1,r,st,ed);re[p]=re[ls]+re[rs];
}
int query(int p,int l,int r,int st,int ed)
{
if(l>ed||r<st) return 0;if(l>=st&&r<=ed) return re[p];
pushdown(p);return query(ls,l,mid,st,ed)+query(rs,mid+1,r,st,ed);
}
signed main()
{
n=read(),k=read();
for(int i=1,u,v,w;i<n;i++) u=read(),v=read(),w=read(),add(u,v,w),add(v,u,w);
dfs1(1,0),dfs2(1,1);build(1,1,n);ans1+=dep[1];
ans2+=query(1,1,n,dfn[1],dfn[1]);modify(1,1,n,dfn[1],dfn[1]);
for(int i=1,x;i<=k;i++)
{
x=read();ans1+=dep[x];
while(x)
{
ans2+=query(1,1,n,dfn[top[x]],dfn[x]);
modify(1,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}print(2*ans1*i-ans2*4);puts("");
}
return 0;
}
```