题解 P3925 【aaa被续】

· · 题解

先膜楼下dalao为敬，然而由于本蒟蒻太菜了，只会树剖的nlog^2n卡常做法

30分做法：

暴力续aaa，乖乖♂站好即可

50分做法：

考虑每个aaa对答案的贡献，每个点以还未续掉的点数为权值，

注意到每个点续掉每个aaa时权值都会-1 (-1s), 因此先续码力大的aaa总是对的，排完序每次跳到根，路径系数-1即可。

而且本题要求最大值，却还要在mod的意义下计算，这样贪心求解之后才可以放心膜。

70~100分做法

注意到续aaa的过程每次需要走树上到根的路径，需要搞两个操作：

1.求到根路径的权值和
2.将到根路径权值-1

自然想到树剖

于是打了一发，发现最后一个点TLE了，显然nlog^2n不是正解，但是与时限相差也不大。

于是开始卡常。。。。。。 我们用树状数组代替线段树对链剖进行维护，因为树状数组对上面的操作完全可以胜任，而且常数小！

这样就能AC此题，得到全部的100分。

最后按例代码：

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define maxn 500666
#define mod 1000000007LL
#define mid ((l+r)>>1)
LL n,hhh=0;
struct aaa{
    LL va;
    LL po;
};
bool operator < (aaa a1,aaa a2){
    return a1.va<a2.va;
}
priority_queue <aaa> pq;
LL fa[maxn]={0},w[maxn]={0};
vector <LL> ed[maxn];
LL hs[maxn]={0},tp[maxn]={0},dfn[maxn]={0},tt=1;
LL cf[maxn]={0};
void dfs1(LL a){
    if(a==0) return;
    w[a]=1;hs[a]=0;
    for(LL b=0;b<ed[a].size();b++)
    if(fa[a]!=ed[a][b])
    {
        fa[ed[a][b]]=a;
        dfs1(ed[a][b]);
        w[a]+=w[ed[a][b]];
        if(w[ed[a][b]]>w[hs[a]]) hs[a]=ed[a][b];
    }
}
void dfs2(LL a){
    if(a==0) return;
    tp[a]= a==hs[fa[a]]? tp[fa[a]]:a;
    dfn[a]=tt++;
    dfs2(hs[a]);
    for(LL b=0;b<ed[a].size();b++)
    if(ed[a][b]!=fa[a]&&ed[a][b]!=hs[a]) dfs2(ed[a][b]);
}
//BIT
LL lowbit(LL x) {return (-x)&x;} 
LL bit[3][maxn]={0};
void add(LL a,LL x,LL c){
    while(x<=n)
    {
        bit[a][x]+=c;
        x+=lowbit(x);
    }
}
LL qu(LL a,LL x){
    LL ret=0;
    while(x)
    {
        ret+=bit[a][x];
        ret%=mod;
        x-=lowbit(x);
    }
    return ret;
}
LL qz(LL x){
    return ((qu(1,x)*(x+1)-qu(2,x))%mod+mod)%mod;
}
//.......
void xu(LL a,LL v){
    LL b,c,d;
    while(a)
    {
        c=tp[a];
        hhh+=(qz(dfn[a])-qz(dfn[c]-1))*v;
        hhh%=mod;
        add(1,dfn[c],-1);
        add(1,dfn[a]+1,1);
        add(2,dfn[c],-dfn[c]);
        add(2,dfn[a]+1,dfn[a]+1);
        a=fa[c];
    }
}
int main(){
    scanf("%lld",&n);
    LL a,b,c,i,j,k;
    aaa tmp;
    for(a=1;a<n;a++)
    {
        scanf("%lld%lld",&i,&j);
        ed[i].push_back(j);
        ed[j].push_back(i);
    }
    for(a=1;a<=n;a++)
    {
        scanf("%lld",&b);
        tmp.va=b;tmp.po=a;
        pq.push(tmp);
    }
    dfs1(1);dfs2(1);
    for(a=1;a<=n;a++) cf[dfn[a]]=w[a];
    for(a=n;a>=1;a--) cf[a]-=cf[a-1];
    for(a=1;a<=n;a++) add(1,a,cf[a]);
    for(a=1;a<=n;a++) add(2,a,cf[a]*a);
    while(pq.size())
    {
        tmp=pq.top();pq.pop();
        xu(tmp.po,tmp.va);
    }
    printf("%lld\n",hhh);
    return 0;
}