简单 \(DP\) 。考虑 \(f(i,0/1)\) 表示以 \(i\) 为根的子树, \(i\) 个选的权值类型为 \(0/1\),的最大贡献和。

主要是如何转移。注意到 \(\lceil \frac{x_i}{1000} \rceil\) ,可以直接枚举极差 \(x_i=0,1000,2000...\) ,然后每次 \(2-pointer\) 枚举, 每个节点有两种取值,当两种都落在区间内时就取优的,否则只能取在区间内的那个。复杂度 \(O(n*100)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
#define _X first
#define _Y second
#define mp make_pair
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int getint(){
char ch=gc(); int res=0,ff=1;
while(!isdigit(ch)) ch=='-'?ff=-1:0, ch=gc();
while(isdigit(ch)) res=(res<<3)+(res<<1)+ch-'0', ch=gc();
return res*ff;
}
using namespace std;
typedef long long LL;
const int maxn=100005,maxe=200005;
int n,p[maxn][2],c[maxn];
LL f[maxn][2];
int fir[maxn],nxt[maxe],son[maxe],tot;
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
int v[maxn];
pair<int,pair<int,int>> q[maxn*2];
void dfs(int x,int pre){
for(int j=fir[x];j;j=nxt[j]) if(son[j]!=pre) dfs(son[j],x);
v[0]=0;
for(int j=fir[x];j;j=nxt[j])
if(son[j]!=pre){
v[++v[0]]=son[j];
q[v[0]*2-1]=mp(p[son[j]][0],mp(son[j],0));
q[v[0]*2]=mp(p[son[j]][1],mp(son[j],1));
}
f[x][0]=p[x][0]; f[x][1]=p[x][1];
if(!v[0]) return;
v[++v[0]]=x;
q[v[0]*2-1]=mp(p[x][0],mp(x,0));
q[v[0]*2]=mp(p[x][1],mp(x,1));
sort(q+1,q+v[0]*2+1);
LL tmp[2]; tmp[0]=tmp[1]=f[0][0];
for(int d=0;d<=100000;d+=1000){
LL res=-(LL)(d/1000)*666*x; int num=0;
for(int i=1;i<=v[0];i++) c[v[i]]=-1;
for(int i=1,lst=0;i<=v[0]*2;){
while(lst<v[0]*2&&q[lst+1]._X<=q[i]._X+d){
int t=q[++lst]._Y._X;
if(q[lst]._Y._Y==0) num++, res+=f[t][c[t]=0]; else{
if(c[t]!=-1) res-=f[t][c[t]], res+=f[t][c[t]=(f[t][1]>f[t][0])];
else num++, res+=f[t][c[t]=1];
}
}
if(num==v[0]){
tmp[c[x]]=max(tmp[c[x]],res);
if(q[i]._X<=p[x][0]&&p[x][0]<=q[i]._X+d&&q[i]._X<=p[x][1]&&p[x][1]<=q[i]._X+d)
tmp[c[x]^1]=max(tmp[c[x]^1],res-f[x][c[x]]+f[x][c[x]^1]);
}
if(lst==v[0]*2) break;
int j=i;
bool pd=false;
while(j<=v[0]*2&&q[i]._X==q[j]._X){
int t=q[j]._Y._X;
if(q[j]._Y._Y==0){
if(p[t][1]<=q[i]._X+d) res-=f[t][c[t]], res+=f[t][c[t]=1];
else res-=f[t][c[t]], num--, c[t]=-1;
} else pd=true;
j++;
}
if(pd) break;
i=j;
}
}
f[x][0]=tmp[0]; f[x][1]=tmp[1];
}
int main(){
freopen("jsk11148.in","r",stdin);
freopen("jsk11148.out","w",stdout);
n=getint();
for(int i=1;i<=n;i++){
p[i][0]=getint(); p[i][1]=getint();
if(p[i][0]>p[i][1]) swap(p[i][0],p[i][1]);
}
for(int i=1;i<=n-1;i++){
int x=getint(),y=getint();
add(x,y); add(y,x);
}
memset(f,192,sizeof(f));
dfs(1,1);
printf("%lld\n",max(f[1][0],f[1][1]));
return 0;
}