每日一题 6月18日 颓红警 树形DP-维护区间平方差距离

题目链接：https://ac.nowcoder.com/acm/problem/19314
题目大意：就是有一棵树，每个节点有一个防御力mi[i], 你的攻击力为P，你1是根节点，每次你可以选择一个节点i进行攻击，对i造成的伤害为P，对i的子孙j造成 的伤害，并且攻击i节点时，保证他的所有祖先全部被击败，mi[i]<0就被击败。问你最少的攻击次数，把树上节点全部打败。
思路：

ps:siz[], di1[], di2[]:直接维护1-i的前缀和会爆LL

#include<bits/stdc++.h>
#define LL long long
using namespace std;

LL mi[1000005];
vector<vector<LL> > v(1000005);
LL len, n, p;
LL di2[1000005], di1[1000005], siz[1000005], cnt[1000005], ans=0;
void DFS(LL u, LL fa, LL d){
    if(d>len){//减去之前不会造成影响祖先的贡献
        LL t=d-len;
        siz[u]-=cnt[t];
        di1[u]-=cnt[t]*t;
        di2[u]-=cnt[t]*t*t;
    }
    mi[u]-=siz[u]*(p-d*d)-di2[u]+2*di1[u]*d;
    LL pos=0;
    if(mi[u]>=0){
        pos=(mi[u])/p+1; ans+=pos;
    }
    cnt[d]=pos;
    for(auto x: v[u]){
        if(x!=fa){
            siz[x]=siz[u]+pos; di1[x]=di1[u]+d*pos; di2[x]=di2[u]+pos*d*d;
            DFS(x, u, d+1);
        }
    }
}

int main(){

    LL x, y; scanf("%lld%lld", &n, &p);
    len=sqrt(p)+1;
    for(LL i=1; i<=n; i++){
        scanf("%lld", &mi[i]);
    }
    for(LL i=1; i<n; i++){
        scanf("%lld%lld", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    DFS(1, 0, 1);
    cout<<ans<<endl;

    return 0;
}