题意：
给定n个点的树，每个点有一个权值a(i)， 要求找到两个不同的点S和T，满足a(T)-a(S)-dist(S,T)最大，dist(x,y)是点x和y的树上距离。 输出最大值。
数据范围：n<=1e5
解法：
题目给的是树
,很容易往树形dp想
,但是树形dp应该很难写
,挺坑的
.
建立源点
0,向n个点建立有向边
,边权为
-a
[i
],
建立汇点n
+1,n个点都向它有向边
,边权为a
[i
],
令原图的双向边边权取反变为负数
,
那么点
0到点n
+1的最短路就是式子的答案
.
code：
#include<bits/stdc++.h>
using namespace std
;
const int maxm
=1e5+5;
int head
[maxm
],nt
[maxm
<<2],to
[maxm
<<2],w
[maxm
<<2],tot
;
int mark
[maxm
];
int d
[maxm
];
int a
[maxm
];
int n
;
void add(int x
,int y
,int z
){
tot
++;nt
[tot
]=head
[x
];head
[x
]=tot
;to
[tot
]=y
;w
[tot
]=z
;
}
void spfa(int st
){
queue
<int>q
;
q
.push(st
);
for(int i
=1;i
<=n
+1;i
++){
d
[i
]=-1e9;
mark
[i
]=0;
}
d
[st
]=0;
mark
[st
]=1;
while(!q
.empty()){
int x
=q
.front();q
.pop();
mark
[x
]=0;
for(int i
=head
[x
];i
!=-1;i
=nt
[i
]){
int v
=to
[i
];
if(d
[v
]<d
[x
]+w
[i
]){
d
[v
]=d
[x
]+w
[i
];
if(!mark
[v
]){
mark
[v
]=1;
q
.push(v
);
}
}
}
}
}
signed main(){
int T
;scanf("%d",&T
);
while(T
--){
scanf("%d",&n
);
for(int i
=0;i
<=n
+1;i
++){
head
[i
]=-1;
}
tot
=1;
for(int i
=1;i
<=n
;i
++){
scanf("%d",&a
[i
]);
}
for(int i
=1;i
<n
;i
++){
int a
,b
,c
;scanf("%d%d%d",&a
,&b
,&c
);
add(a
,b
,-c
);
add(b
,a
,-c
);
}
for(int i
=1;i
<=n
;i
++){
add(0,i
,-a
[i
]);
}
for(int i
=1;i
<=n
;i
++){
add(i
,n
+1,a
[i
]);
}
spfa(0);
printf("%d\n",d
[n
+1]);
}
return 0;
}
