Snacks
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1779 Accepted Submission(s): 427
Problem Description
百度科技园内有n
个零食机，零食机之间通过n−1
条路相互连通。每个零食机都有一个值v
，表示为小度熊提供零食的价值。
由于零食被频繁的消耗和补充，零食机的价值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") `
Output
对于每组数据，首先输出一行”Case #?:”，在问号处应填入当前数据的组数，组数从1开始计算。
对于每次询问，输出从编号为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
Sample Output
Case #1:
102
27
2
20
Source
题意：中文题面
题解：第一次写线段树+dfs序列
/******************************
code by drizzle
blog: www.cnblogs.com/hsd-/
^ ^ ^ ^
O O
******************************/
#include<bits/stdc++.h>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<vector>
#include<string>
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define A first
#define B second
const int mod=;
const int MOD1=;
const int MOD2=;
const double EPS=0.00000001;
//typedef long long ll;
typedef __int64 ll;
const ll MOD=;
const int INF=;
const ll MAX=1ll<<;
const double eps=1e-;
const double inf=~0u>>;
const double pi=acos(-1.0);
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
int T,n,m,x,judge,nedge=,dfn, y;
struct node
{
int ed;
int pre;
} N[];
int pre[],in[],out[];
ll v[];
ll seq[];
ll fuck;
struct tree
{
int l,r;
ll lazy;
ll maxn;
} tree[];
inline void add(int st,int ed)
{
nedge++;
N[nedge].ed=ed;
N[nedge].pre=pre[st];
pre[st]=nedge;
}
inline void getdfs(int x,int y,ll s)
{
s+=v[x];
in[x]=++dfn;
seq[dfn]=s;
for(int i=pre[x]; i; i=N[i].pre)
{
if(N[i].ed!=y)
{
getdfs(N[i].ed,x,s);
}
}
out[x]=dfn;
}
inline void pushdown(int root)
{
if(tree[root].lazy==) return;
tree[root<<].lazy+=tree[root].lazy;
tree[root<<|].lazy+=tree[root].lazy;
tree[root<<].maxn+=tree[root].lazy;
tree[root<<|].maxn+=tree[root].lazy;
tree[root].lazy=;
}
inline void buildtree(int root,int left,int right)
{
tree[root].l=left;
tree[root].r=right;
tree[root].lazy=;
if(left==right)
{
tree[root].maxn=seq[left];
return ;
}
int mid=(left+right)>>;
buildtree(root<<,left,mid);
buildtree(root<<|,mid+,right);
tree[root].maxn=max(tree[root<<].maxn,tree[root<<|].maxn);
}
inline void updata(int root,int in,int out,ll after)
{
if(in==tree[root].l&&tree[root].r==out)
{
tree[root].lazy+=after;
tree[root].maxn+=after;
return ;
}
pushdown(root);
int mid=(tree[root].l+tree[root].r)>>;
if(out<=mid)
updata(root<<,in,out,after);
else
{
if(in>mid)
updata(root<<|,in,out,after);
else
{
updata(root<<,in,mid,after);
updata(root<<|,mid+,out,after);
}
}
tree[root].maxn=max(tree[root<<].maxn,tree[root<<|].maxn);
}
inline ll query(int root,int in,int out)
{
if(in==tree[root].l&&tree[root].r==out)
{
return tree[root].maxn;
}
pushdown(root);
int mid=(tree[root].l+tree[root].r)>>;
if(out<=mid)
return query(root<<,in,out);
else
{
if(in>mid)
return query(root<<|,in,out);
else
return max(query(root<<,in,mid),query(root<<|,mid+,out));
}
}
void init()
{
memset(tree,,sizeof(tree));
memset(N,,sizeof(N));
memset(pre,,sizeof(pre));
memset(in,,sizeof(in));
memset(out,,sizeof(out));
memset(v,,sizeof(v));
memset(seq,,sizeof(seq));
nedge=;
dfn=;
}
int main()
{
scanf("%d",&T);
for(int i=; i<=T; i++)
{
init();
scanf("%d %d",&n,&m);
for(int j=; j<n; j++)
{
scanf("%d %d",&x,&y);
x++;
y++;
add(x,y);
add(y,x);
}
for(int j=; j<=n; j++)
scanf("%I64d",&v[j]);
getdfs(,,);
buildtree(,,n);
printf("Case #%d:\n",i);
for(int j=; j<=m; j++)
{
scanf("%d %d",&judge,&x);
if(judge==)
{
scanf("%I64d",&fuck);
x++;
ll exm=fuck;
fuck=fuck-v[x];
updata(,in[x],out[x],fuck);
v[x]=exm;
}
else
{
x++;
printf("%I64d\n",query(,in[x],out[x]));
}
}
}
return ;
}