算法训练 结点选择
时间限制：1.0s 内存限制：256.0MB
问题描述
有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？
输入格式
第一行包含一个整数 n 。
接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。
接下来一共 n-1 行，每行描述树上的一条边。
输出格式
输出一个整数，代表选出的点的权值和的最大值。
样例输入
5
1 2 3 4 5
1 2
1 3
2 4
2 5
1 2 3 4 5
1 2
1 3
2 4
2 5
样例输出
12
样例说明
选择3、4、5号点，权值和为 3+4+5 = 12 。
数据规模与约定
对于20%的数据， n <= 20。
对于50%的数据， n <= 1000。
对于100%的数据， n <= 100000。
权值均为不超过1000的正整数。
注意：用了链表数组存路径。
下面的代码超时了！！！
import java.util.Scanner;
public class Main {
public static node[] t = new node[400000];
public static long n, m, ans = 0, Max = -0x3f3f3f3f;
public static Scanner cin = new Scanner(System.in);
public static void main(String[] args) {
// TODO Auto-generated method stub
n = cin.nextLong();
m = cin.nextLong();
build(1, n, 1);
while(m-- != 0){
int i, x, y;
Max = -0x3f3f3f3f; //每次都要初始化
ans = 0;
i = cin.nextInt();
x = cin.nextInt();
y = cin.nextInt();
if(i == 1){
update(x, y, 1);
}
else if(i == 2){
query(x, y, 1);
// cout << ans << endl;
System.out.println(ans);
}
else if(i == 3){
query(x, y, 1);
// cout << Max << endl;
System.out.println(Max);
}
}
}
static void build(long l, long r, int k){
t[k] = new node(); // 因为是对象数组，所以必须要new出对象，才能用
t[k].l = l;
t[k].r = r;
if(l == r){
// cin >> t[k].v;
t[k].v = cin.nextLong();
t[k].s = t[k].v;
return ; //每个查找完都要结束
}
long mid = (l + r) / 2;
build(l, mid, k * 2);
build(mid + 1, r, k * 2 + 1);
t[k].v = Math.max(t[k * 2].v, t[k * 2 + 1].v);
t[k].s = t[k * 2].s + t[k * 2 + 1].s;
}
static void update(int c, int v, int k){
if(t[k].l == t[k].r && t[k].l == c){
t[k].v = v;
t[k].s = v; //这个也要改才行哇！！！
return ; //每个查找玩，都要结束
}
long mid = (t[k].l + t[k].r) / 2;
if(c <= mid){
update(c, v, k * 2);
}
else{
update(c, v, k * 2 + 1);
}
t[k].v = Math.max(t[k * 2].v, t[k * 2 + 1].v);
t[k].s = t[k * 2].s + t[k * 2 + 1].s;
}
static void query(long l, long mid2, int k){
if(t[k].r < l || t[k].l > mid2){
return ;
}
if(l <= t[k].l && mid2 >= t[k].r){
ans += t[k].s;
if(Max < t[k].v){
Max = t[k].v;
}
return ; //查找玩要立即结束
}
long mid = (t[k].l + t[k].r) / 2; //这里是节点的区间中点
if(mid > mid2){
query(l, mid2, k * 2);
}
else if(mid < l){
query(l, mid2, k * 2 + 1);
}
else{
query(l, mid, k * 2);
query(mid + 1, mid2, k * 2 + 1);
}
}
}
class node{
public long l;
public long r;
public long v, s;
}