不灭僵魂,纳耶里海礁,沈阳植物园门票多少钱
令1为树根，t=σd[i],sum[x]是子树x中的d之和，dis[x]是节点x的带权深度。
对于节点x的儿子y，边长为w，如果y比x更优，则(t-sum[y])*w-sum[y]*w<=0即sum[y]>=t/2。
换句话说，若存在sum[y]>t/2，显然y更优，且y只存在一个（对于x）；若存在sum[y]=t/2，(1个或2个)，因为y的子树内都不存在sum>t/2的点，所以y就是一个最优解，不必递归地做。
考虑一类暴力求出最优点：从根出发依次进入sum>t/2的儿子，最深的那个点即为带权重心。这可以树剖维护sum/区间最大值，如果右半区间(较深)存在>=t/2，即向右跳转。
设已经求出了最优点r，答案是σ(d[i]*dis[i]+d[i]*dis[r]-2*d[i]*dis[lca(r,i)])，套路地维护就行了。
意外的简单？
我要评论#include <bits/stdc++.h>
#define ll long long
#define trvl(x,i,y) for(int i=ehd[x],y; y=to[i],i; i=lst[i])
#define ls (x<<1)
#define rs (x<<1|1)
using namespace std;
const int n=1e5+10;
int n,m;
int ehd[n],to[n<<1],len[n<<1],lst[n<<1];
int fa[n],siz[n],son[n],top[n],id[n],dfn[n];
ll s,t,dis[n];
void insert(int x,int y,int w) {
static int cnt=0;
to[++cnt]=y,len[cnt]=w,lst[cnt]=ehd[x],ehd[x]=cnt;
to[++cnt]=x,len[cnt]=w,lst[cnt]=ehd[y],ehd[y]=cnt;
}
void dfs1(int x,int p) {
fa[x]=p; siz[x]=1;
trvl(x,i,y) if(y!=p) {
dis[y]=dis[x]+len[i];
dfs1(y,x);siz[x]+=siz[y];
if(siz[y]>siz[son[x]]) son[x]=y;
}
}
void dfs2(int x,int t) {
static int cnt=0;
top[dfn[id[x]=++cnt]=x]=t;
if(son[x]) dfs2(son[x],t);
trvl(x,i,y) if(son[x]!=y&&fa[x]!=y) dfs2(y,y);
}
int tag[n<<2],mx[n<<2];
ll c[n<<2],s[n<<2];
void psd(int x) {
if(!tag[x]) return;
c[ls]+=s[ls]*tag[x],mx[ls]+=tag[x],tag[ls]+=tag[x];
c[rs]+=s[rs]*tag[x],mx[rs]+=tag[x],tag[rs]+=tag[x];
tag[x]=0;
}
void upd(int x) {
mx[x]=max(mx[ls],mx[rs]);
c[x]=c[ls]+c[rs];
}
void build(int x,int l,int r) {
if(l==r) {
s[x]=dis[dfn[l]]-dis[fa[dfn[l]]];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
s[x]=s[ls]+s[rs];
}
int find(int x,int l,int r) {
if(l==r) return dfn[l];
int mid=(l+r)>>1; psd(x);
if(mx[rs]*2>t) return find(rs,mid+1,r);
return find(ls,l,mid);
}
void mdf(int x,int l,int r,int l,int r,ll w) {
if(l<=l&&r<=r) {
c[x]+=s[x]*w,mx[x]+=w,tag[x]+=w;
return;
}
int mid=(l+r)>>1; psd(x);
if(l<=mid) mdf(ls,l,mid,l,r,w);
if(mid<r) mdf(rs,mid+1,r,l,r,w);
upd(x);
}
ll qry(int x,int l,int r,int l,int r) {
if(l<=l&&r<=r) return c[x];
int mid=(l+r)>>1; ll c=0; psd(x);
if(l<=mid) c+=qry(ls,l,mid,l,r);
if(mid<r) c+=qry(rs,mid+1,r,l,r);
return c;
}
void modify(int x,int w) {
for(; x; x=fa[top[x]]) mdf(1,1,n,id[top[x]],id[x],w);
}
ll query(int x,ll w=0) {
for(; x; x=fa[top[x]]) w+=qry(1,1,n,id[top[x]],id[x]);
return w;
}
int main() {
scanf("%d%d",&n,&m);
for(int x,y,w,i=n; --i; ) {
scanf("%d%d%d",&x,&y,&w);
insert(x,y,w);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
for(int x,w; m--; ) {
scanf("%d%d",&x,&w);
modify(x,w);
s+=dis[x]*w;
t+=w;
x=find(1,1,n);
printf("%lld\n",s+t*dis[x]-2*query(x));
}
return 0;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论