Snacks
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 4446 Accepted Submission(s): 980
Problem Description
百度科技园内有n个零食机，零食机之间通过n−1条路相互连通。每个零食机都有一个值v，表示为小度熊提供零食的价值。
由于零食被频繁的消耗和补充，零食机的价值v会时常发生变化。小度熊只能从编号为0的零食机出发，并且每个零食机至多经过一次。另外，小度熊会对某个零食机的零食有所偏爱，要求路线上必须有那个零食机。
为小度熊规划一个路线，使得路线上的价值总和最大。
由于零食被频繁的消耗和补充，零食机的价值v会时常发生变化。小度熊只能从编号为0的零食机出发，并且每个零食机至多经过一次。另外，小度熊会对某个零食机的零食有所偏爱，要求路线上必须有那个零食机。
为小度熊规划一个路线，使得路线上的价值总和最大。
Input
输入数据第一行是一个整数T(T≤10)，表示有T组测试数据。
对于每组数据，包含两个整数n,m(1≤n,m≤100000)，表示有n个零食机，m次操作。
接下来n−1行，每行两个整数x和y(0≤x,y<n)，表示编号为x的零食机与编号为y的零食机相连。
接下来一行由n个数组成，表示从编号为0到编号为n−1的零食机的初始价值v(|v|<100000)。
接下来m行，有两种操作：0 x y，表示编号为x的零食机的价值变为y；1 x，表示询问从编号为0的零食机出发，必须经过编号为x零食机的路线中，价值总和的最大值。
本题可能栈溢出，辛苦同学们提交语言选择c++，并在代码的第一行加上：
`#pragma comment(linker, "/STACK:1024000000,1024000000") `
对于每组数据，包含两个整数n,m(1≤n,m≤100000)，表示有n个零食机，m次操作。
接下来n−1行，每行两个整数x和y(0≤x,y<n)，表示编号为x的零食机与编号为y的零食机相连。
接下来一行由n个数组成，表示从编号为0到编号为n−1的零食机的初始价值v(|v|<100000)。
接下来m行，有两种操作：0 x y，表示编号为x的零食机的价值变为y；1 x，表示询问从编号为0的零食机出发，必须经过编号为x零食机的路线中，价值总和的最大值。
本题可能栈溢出，辛苦同学们提交语言选择c++，并在代码的第一行加上：
`#pragma comment(linker, "/STACK:1024000000,1024000000") `
Output
对于每组数据，首先输出一行”Case #?:”，在问号处应填入当前数据的组数，组数从1开始计算。
对于每次询问，输出从编号为0的零食机出发，必须经过编号为x零食机的路线中，价值总和的最大值。
对于每次询问，输出从编号为0的零食机出发，必须经过编号为x零食机的路线中，价值总和的最大值。
Sample Input
1
6 5
0 1
1 2
0 3
3 4
5 3
7 -5 100 20 -5 -7
1 1
1 3
0 2 -1
1 1
1 5
6 5
0 1
1 2
0 3
3 4
5 3
7 -5 100 20 -5 -7
1 1
1 3
0 2 -1
1 1
1 5
Sample Output
Case #1:
102
27
2
20
102
27
2
20
Source
Recommend
Well不太会写
贴几个博客链接吧
dfs序https://acm.sjtu.edu.cn/w/images/3/35/%E6%A0%91%E7%9A%84dfs%E5%BA%8F%E5%8F%8A%E5%85%B6%E5%BA%94%E7%94%A8%EF%BC%88%E9%97%AB%E9%B8%BF%E5%AE%87%EF%BC%89.pdf
线段树
http://www.cnblogs.com/TenosDoIt/p/3453089.html
lazy操作
https://blog.csdn.net/xs18952904/article/details/72763467
以及 题解
http://www.cnblogs.com/liyinggang/p/5925196.html
这是一条已经看懂的分割线
基本就是按照题解写的思路
先dfs遍历所有的路径 确定dfs序 这个序就是未来线段树的的基础
相当于线段树的先序遍历
用这些节点建立线段树 转换成了求区间最大值
RE 了一发是因为cnt忘记初始化了
WA了一发是因为inf定的0x3f3f3f3f太小了 改成1e18就过了
类型改成longlong的时候inf也要记得改过来
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 1e18
using namespace std;
const int maxn = 100005;
int n, t, m;
struct node{
int v, next;
}edges[maxn << 2];
int head[maxn], tot, cnt;//tot为边的数量 cnt用于标记dfs序
int in[maxn] ,out[maxn];
long long lazy[maxn << 2];
long long dis[maxn], b[maxn];
long long sum[maxn << 2], cost[maxn];
void init()
{
memset(head, -1, sizeof(head));
tot = cnt = 0;
}
void addedge(int u, int v, int &k)
{
edges[k].v = v;
edges[k].next = head[u];
head[u] = k++;
}
void pushup(int idx)
{
sum[idx] = max(sum[idx<<1], sum[idx<<1|1]);
}
void pushdown(int idx)
{
if(lazy[idx]){
sum[idx<<1] += lazy[idx];
sum[idx<<1|1] += lazy[idx];
lazy[idx<<1] += lazy[idx];
lazy[idx<<1|1] += lazy[idx];
lazy[idx] = 0;
}
return;
}
void build(int l, int r, int root)
{
lazy[root] = 0;
if(l == r){
sum[root] = b[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, root << 1);
build(mid + 1, r, root << 1 | 1);
pushup(root);
}
void update(int l, int r, int ll, int rr, int idx, int val)
{
//让l和r进入llrr的区间内
if(l >= ll && r <= rr){
sum[idx] = sum[idx] + val;//val为变化量
lazy[idx] = lazy[idx] + val;
return;
}
int mid = (l + r) >> 1;
pushdown(idx);
if(mid >= ll) update(l, mid, ll, rr, idx << 1, val);
if(mid < rr) update(mid + 1, r, ll, rr, idx << 1 | 1, val);
pushup(idx);
}
long long mm = -1;
void query(int l, int r, int ll, int rr, int idx)
{
if(l >= ll && r <= rr){
mm = max(mm, sum[idx]);
return;
}
int mid = (l + r) >> 1;
pushdown(idx);
if(mid >= ll) query(l, mid, ll, rr, idx << 1);
if(mid < rr) query(mid + 1, r, ll, rr, idx << 1 | 1);
}
void dfs(int u, int pre)
{
//cnt标记dfs序
in[u] = ++cnt;
b[cnt] = dis[u];
for(int k = head[u]; k != -1; k = edges[k].next){
int v = edges[k].v;
if(v == pre) continue;
dis[v] = dis[u] + cost[v];
dfs(v, u);
}
out[u] = cnt;
}
int main()
{
cin>>t;
for(int cas = 1; cas <= t; cas++){
init();
scanf("%d%d", &n, &m);
for(int i = 0; i < n - 1; i++){
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v, tot);
addedge(v, u, tot);
}
for(int i = 0; i < n; i++){
scanf("%lld", &cost[i]);
}
dis[0] = cost[0];
dfs(0, -1);//dfs路径 dfs序
build(1, n, 1);
printf("Case #%d:\n", cas);
while(m--){
int op, x, y;
scanf("%d", &op);
if(op == 1){
scanf("%d", &x);
mm = -inf;
query(1, n, in[x], out[x], 1);
printf("%lld\n", mm);
}
else{
scanf("%d%d", &x, &y);
long long change = (long long)y - cost[x];
update(1, n, in[x], out[x], 1, change);
cost[x] = y;
}
}
}
return 0;
}