T4[树上数据结构/套路]给出n个点无向树，每个点有点权，小A从n个点中随机选择1个作为关键节点，价值随机选择另一个节点的\(ai*dis(ai,key)(ai<akey)\)。求价值的期望。(n<=8e5)
考场
贡献独立，单独考虑每个点的贡献：
\(\sum ai*dis(ai,chs)=(\sum dep_{ai}+dep_{a_{chs}}-dep_{lca}\))*a[chs]
然后发现拆了我也不会统计（lca怎么办？），直接菊花链特判+暴力水48分
结果水了32分
剩下那个T了，不知道为什么。
正解
经典套路：把点按照权值sort一下，前面2个dep随便统计，lca就加入这个节点就把从x到root的路径+1，统计x就统计到root的权值和
点击查看代码
// ubsan: undefined
// accoders
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define chu printf
#define rint register int
inline ll re()
{
ll x=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')h=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*h;
}
const int mod=998244353;
const int Z=8e5+100;
int n,m,a[Z],head[Z],tot;
int dep[Z],siz[Z],mson[Z],top[Z],dfn[Z],tim,p[Z],sdep[Z],fa[Z];
struct node
{
int to,nxt;
}e[Z<<1];
inline void upd(int & x,int y)
{
x=x+y;
x=(x>=mod)?(x-mod):(x);
}
inline void add_e(int x,int y)
{
e[++tot].to=y;e[tot].nxt=head[x];
head[x]=tot;
}
inline ll qpow(ll a,ll b)
{
ll c=1;
while(b)
{
if(b&1)c=1ll*c*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
struct segmentTreee//维护区间加，区间查询,int
{
int sum[Z<<2],tag[Z<<2];
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mid ((l+r)>>1)
inline void pushdown(int rt,int l,int r)
{
if(!tag[rt])return;
upd(sum[lson],1ll*tag[rt]*(mid-l+1)%mod);
upd(sum[rson],1ll*tag[rt]*(r-mid)%mod);
upd(tag[lson],tag[rt]);
upd(tag[rson],tag[rt]);
tag[rt]=0;
}
inline void pushup(int rt)
{
int x=0;
upd(x,sum[lson]+sum[rson]);
sum[rt]=x;
}
inline void insert(int rt,int l,int r,int L,int R,int vl)
{
if(L<=l&r<=R)
{
upd(sum[rt],(r-l+1)*vl);
upd(tag[rt],vl);
// chu("sum[%d]:%d\n",rt,sum[rt]);
return;
}
pushdown(rt,l,r);
if(L<=mid)insert(lson,l,mid ,L,R,vl);
if(R>mid)insert(rson,mid+1,r,L,R,vl);
pushup(rt);
//chu("sum[%d]:%d\n",rt,sum[rt]);
}
inline int query(int rt,int l,int r,int L,int R)
{
// chu("arr:%d--%d query(%d--%d)\n",l,r,L,R);
if(L<=l&r<=R)
{
//chu("return:sum[%d]:%d\n",rt,sum[rt]);
return sum[rt];
}
pushdown(rt,l,r);int rel=0;
// chu("%d--%d(%d)%d---%d(%d)\n",l,mid,sum[lson],mid+1,r,sum[rson]);
if(L<=mid)upd(rel,query(lson,l,mid ,L,R));
if(R>mid)upd(rel,query(rson,mid+1,r,L,R));
return rel;
}
}seg;
inline void dfs(int x,int ff)
{
fa[x]=ff,dep[x]=dep[ff]+1;siz[x]=1;
for(rint i=head[x];i;i=e[i].nxt)
{
int to=e[i].to;
if(to==ff)continue;
dfs(to,x);
siz[x]+=siz[to];
if(siz[to]>siz[mson[x]])mson[x]=to;
}
}
inline void slpf(int x,int bl)
{
top[x]=bl;
dfn[x]=++tim;
if(!mson[x])return;
slpf(mson[x],bl);
for(rint i=head[x];i;i=e[i].nxt)
{
int to=e[i].to;
if(top[to])continue;
slpf(to,to);
}
}
inline int query(int x)
{
int rel=0;
// chu("h!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!e query(%d):%d\n",x,rel);
while(top[x]!=top[1])
{
upd(rel,seg.query(1,1,n,dfn[top[x]],dfn[x]));
x=fa[top[x]];
}
//chu("he query:%d--%d\n",dfn[1],dfn[x]);
// chu("now rel:%d(%d--%d)\n",rel,dfn[1],dfn[x]);
upd(rel,seg.query(1,1,n,dfn[1],dfn[x]));
// chu("the sum:%d(%d %d)\n",rel,seg.query(1,1,n,2,2),seg.query(1,1,n,1,1));
return rel;
}
inline void add(int x)
{
int rel=0;
// chu("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!insert(%d)\n",x);
while(top[x]!=top[1])
{
seg.insert(1,1,n,dfn[top[x]],dfn[x],1);
// chu("he insert(%d -- %d):%d\n",dfn[top[x]],dfn[x],1);
x=fa[top[x]];
}
// chu("he insert(%d--%d)\n",dfn[1],dfn[x]);
seg.insert(1,1,n,dfn[1],dfn[x],1);
}
int main()
{
// freopen("challenge3.in","r",stdin);
// freopen("1.out","w",stdout);
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
n=re(),m=re();
for(rint i=1;i<=n;++i)a[i]=m-re();
for(rint i=1;i<n;++i)
{
int u=re(),v=re();
add_e(u,v);add_e(v,u);
}
for(rint i=1;i<=n;++i)p[i]=i;
sort(p+1,p+1+n,[&](const int x,const int y){return a[x]<a[y];});
//return 0;
dfs(1,0);
slpf(1,1);
for(rint i=1;i<=n;++i)upd(sdep[i],(sdep[i-1]+dep[p[i]])%mod);//c//hu("dfn[%d]:%d\n",i,dfn[i]);
int sum=0;
for(rint i=1;i<=n;++i)//扫描每个点
{
int l=i,r=i;
while(r+1<=n&&a[p[r+1]]==a[p[l]])++r;
//l--r 统一计算
for(rint j=l;j<=r;++j)
{
int dev=0;//计算本节点贡献
upd(dev,1ll*dep[p[j]]*(l-1)%mod);
upd(dev,sdep[l-1]);
upd(dev,(mod-2ll*query(p[j])%mod)%mod);//从j到root的路径上，1是root呗
dev=1ll*dev*a[p[j]]%mod;
// chu("for[%d]:the road length is:%d(%d*%d+%d-%d)\n",p[j],dev,dep[p[j]],l-1,sdep[l-1],2*query(p[j]));
upd(sum,dev);
}
for(rint j=l;j<=r;++j)//要把他们算上贡献里
{
add(p[j]);
}
i=r;
}
chu("%lld",1ll*sum*qpow(n,mod-2)%mod*qpow(n-1,mod-2)%mod);
return 0;
}
/*
*/
T2[科普知识，没改]
1,1,1
1,2,3
1,3,5
1,4,8
1,5,12
这个东西竖着看发现是玄学的等差套等差
但是横着看就是组合数！
\(C(i,j)=C(i-1,j-1)+C(i-1,j)\)