题目概述

有 $n$ 个ZZK给JZ打工，他们的上下级关系是一棵树。现在JZ要给蒟蒻ZZK输送一定的神犇之力，每个ZZK可以得到 $r_i$ 点神犇之力或者 $p_i$ 点神犇之力。但是在ZZK得到神犇之力的同时会嫉妒直接下属ZZK得到的神犇之力，嫉妒会使得神犇之力削弱 $\lceil{x\over 1000}\rceil\times 666i$ ，其中 $x$ 是 $i$ 直接下属的神犇之力（不考虑嫉妒）的极差，求 $n$ 个ZZK获得神犇之力的和。

解题报告

显然极差 $1000$ 分一段，所以可以直接枚举极差，然后树形DP+two-pointer一下就行了。

颓太久了调代码能力下降，各种错误调了一个晚上。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=100000;

int n,v[maxn+5][2];LL f[maxn+5][2];
int E,lnk[maxn+5],nxt[(maxn<<1)+5],son[(maxn<<1)+5];
int now,ha[maxn+5];pair<int,int> w[(maxn<<1)+5];

#define Add(x,y) son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E
inline int ID(int L,int R,int x){
    bool A=L<=v[x][0]&&v[x][0]<=R,B=L<=v[x][1]&&v[x][1]<=R;
    if (A&&B) return 3;if (A) return 1;if (B) return 2;return 0;
}
void DP(int x,int pre=0){
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) DP(son[j],x);now=0;
    for (int j=lnk[x];j;j=nxt[j])
        if (son[j]!=pre) w[++now]=mp(v[son[j]][0],son[j]),w[++now]=mp(v[son[j]][1],son[j]);
    if (!now) {f[x][0]=v[x][0];f[x][1]=v[x][1];return;}
    w[++now]=mp(v[x][0],x);w[++now]=mp(v[x][1],x);
    sort(w+1,w+1+now);LL MAX[2];MAX[0]=MAX[1]=f[0][0]-1e18;
    for (int D=0;D<=w[now].fr-w[1].fr+1000;D+=1000){
        int tot=0;LL sum=-(LL)D/1000*666*x;
        for (int i=1;i<=now;i++) ha[w[i].sc]=0;
        for (int i=1,j=1,k,L,R;i<=now;i=k){
            if (v[x][1]<w[i].fr) break;L=w[i].fr;R=L+D;
            for (;j<=now&&w[j].fr<=R;ha[w[j++].sc]++)
                if (!ha[w[j].sc]) sum+=f[w[j].sc][ID(L,R,w[j].sc)==2],tot++;
                else sum+=max(f[w[j].sc][0],f[w[j].sc][1])-f[w[j].sc][0];
            if (tot==(now>>1)){
                int tp=ID(L,R,x);
                if (tp==1||tp==3) MAX[0]=max(MAX[0],sum+v[x][0]);
                if (tp==2||tp==3) MAX[1]=max(MAX[1],sum+v[x][1]);
            }
            for (k=i;k<=now&&w[i].fr==w[k].fr;ha[w[k++].sc]--)
                if (ha[w[k].sc]==1) sum-=f[w[k].sc][ID(L,R,w[k].sc)==2],tot--;
                else sum-=max(f[w[k].sc][0],f[w[k].sc][1])-f[w[k].sc][1];
        }
    }
    f[x][0]=MAX[0];f[x][1]=MAX[1];
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (int i=(scanf("%d",&n),1);i<=n;i++)
        {scanf("%d%d",&v[i][0],&v[i][1]);if (v[i][0]>v[i][1]) swap(v[i][0],v[i][1]);}
    for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
    return DP(1),printf("%lld\n",max(f[1][0],f[1][1])),0;
}