自傷無色 题解
万弘
·
·
题解
套路题。
考虑Dsu on tree.
考虑加入一个 b ,对所有 a\ge b 产生贡献。 [a-b+1,a+b-1] 贡献了 2b-1 个三角，权值和为 a(2b-1)+b(2b-1)+2a(2b-1)/2 .
类似的，可以考虑对 a<b 产生贡献。
值域较大，直接的想法是用平衡树，维护和、平方和，然后单点修改区间询问。平衡树常数比较大可能是过不去的。
冷静一下发现，用到的值形如 dis_x-dis_u 的形式，其中 u 是当前求解的子树的根.用数据结构维护 dis_x ，相对大小同样不变，计算贡献时加上 -dis_u 这个偏移即可。
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<random>
#include<chrono>
typedef long long ll;
typedef unsigned un;
typedef std::vector<int> P;
typedef std::pair<int,int> pii;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
template <typename T> bool umax(T& a,T t){if(t>a)return a=t,1;return 0;}
template <typename T> bool umin(T& a,T t){if(t<a)return a=t,1;return 0;}
/**********/
const int MAXN = 100011,mod = 1e9+7;
ll Qpow(ll a,ll p)
{
ll res=1;
while(p){if(p&1)res=res*a%mod;a=a*a%mod,p>>=1;}
return res;
}
struct Mint
{
int x;
Mint(){x=0;}
Mint(ll x):x((x%mod+mod)%mod) {}
Mint operator* (Mint you){return ll(x)*you.x%mod;}
Mint operator+ (Mint you){return x+you.x<mod?x+you.x:x+you.x-mod;}
void operator+= (Mint you){x+=you.x;if(x>=mod)x-=mod;}
Mint operator- (Mint you){return x-you.x<0?x-you.x+mod:x-you.x;}
void operator-= (Mint you){x-=you.x;if(x<0)x+=mod;}
};
struct edge{int v,w,nxt;}e[MAXN<<1|1];
int cnt=0,last[MAXN];
void adde(int u,int v,int w){e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=last[u],last[u]=cnt;}
int fa[MAXN],size[MAXN],ms[MAXN],diff=0;
Mint ans,c;
ll fx[MAXN],dis[MAXN];
int pos[MAXN];
std::vector<int>a[MAXN];
struct BIT
{
Mint t[MAXN],tot;
#define lowb (i&-i)
void modify(int i,Mint k)
{
tot+=k;
while(i<=diff)t[i]+=k,i+=lowb;
}
Mint Qsum(int i)
{
Mint res=0;
while(i)res+=t[i],i-=lowb;
return res;
}
}t0,t1,t2;
void dfs1(int u)
{
size[u]=1;
for(int i=last[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa[u])continue;
fa[v]=u,dis[v]=dis[u]+e[i].w, dfs1(v),size[u]+=size[v];
if(size[v]>size[ms[u]])ms[u]=v;
}
}
void calc(int u,Mint k)
{
Mint s0=t0.Qsum(pos[u]),s1=t1.Qsum(pos[u]),s2=t2.Qsum(pos[u]);
//As A
Mint A(dis[u]-k.x);
ans+=A*(s1-s0*k)*4;
ans-=A*s0*2;
ans+=(s2-s1*k*2+k*k*s0)*2;
ans-=s1-s0*k;
c+=(s1-s0*k)*2-s0;
//As b
s0=t0.tot-s0,s1=t1.tot-s1,s2=t2.tot-s2;
Mint B=A;
ans+=B*(s1-s0*k)*4;
ans-=(s1-s0*k)*2;
ans+=s0*B*B*2;
ans-=s0*B;
c+=(B*2-1)*s0;
for(int i=last[u];i;i=e[i].nxt)
if(e[i].v!=fa[u])calc(e[i].v,k);
}
void push(int u)
{
t0.modify(pos[u],1),t1.modify(pos[u],dis[u]%mod);
t2.modify(pos[u],(dis[u]%mod)*(dis[u]%mod)%mod);
for(int i=last[u];i;i=e[i].nxt)
if(e[i].v!=fa[u])push(e[i].v);
}
void back(int u)
{
t0.modify(pos[u],Mint(-1)),t1.modify(pos[u],Mint(-dis[u]));
t2.modify(pos[u],Mint(-(dis[u]%mod)*(dis[u]%mod)%mod));
for(int i=last[u];i;i=e[i].nxt)
if(e[i].v!=fa[u])back(e[i].v);
}
void solve(int u)
{
for(int i=last[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa[u]||v==ms[u])continue;
solve(v),back(v);
}
if(ms[u])solve(ms[u]);
for(int i=last[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa[u]||v==ms[u])continue;
calc(v,dis[u]),push(v);
}
t0.modify(pos[u],1),t1.modify(pos[u],dis[u]%mod);
t2.modify(pos[u],(dis[u]%mod)*(dis[u]%mod)%mod);
}
int main()
{
int n=read();
for(int i=1;i<n;++i){int u=read(),v=read(),w=read();adde(u,v,w),adde(v,u,w);}
dfs1(1);
for(int i=1;i<=n;++i)fx[++diff]=dis[i];
std::sort(fx+1,fx+diff+1),diff=std::unique(fx+1,fx+diff+1)-fx-1;
for(int i=1;i<=n;++i)pos[i]=std::lower_bound(fx+1,fx+diff+1,dis[i])-fx;
solve(1);
printf("%lld\n",(ans.x*Qpow(c.x,mod-2)%mod+mod)%mod);
return 0;
}
```