hdu 5692 snacks

hdu 5692 snacks

​​ 百度科技园内有 n n 个零食机，零食机之间通过 n−1 n−1 条路相互连通。每个零食机都有一个值 v v ，表示为小度熊提供零食的价值。

由于零食被频繁的消耗和补充，零食机的价值 v v 会时常发生变化。小度熊只能从编号为0的零食机出发，并且每个零食机至多经过一次。另外，小度熊会对某个零食机的零食有所偏爱，要求路线上必须有那个零食机。

为小度熊规划一个路线，使得路线上的价值总和最大。 Input 输入数据第一行是一个整数 T(T≤10) T(T≤10) ，表示有 T T 组测试数据。

对于每组数据，包含两个整数 n,m(1≤n,m≤100000) n,m(1≤n,m≤100000) ，表示有 n n 个零食机， m m 次操作。

接下来 n−1 n−1 行，每行两个整数 x x 和 y(0≤x,y

#pragma comment(linker, "/STACK:1024000000,1024000000") #include#include#include#define N 110000#define inf 1LL<<63#define ll long longusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f;}int fa[N],T,n,m,num,a[N],in[N],out[N],h[N],root;long long w[N]; struct node{ int y,next;}data[N<<1];struct node2{ ll mx,add;};struct node1{ int l,r,left,right;long long max,lazy;}tree[N<<2];void dfs(int x){ in[x]=++num;w[num]+=a[x]; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (fa[x]==y) continue; fa[y]=x;w[num+1]+=w[in[x]];dfs(y); } out[x]=num;}inline void update(int x){ int l=tree[x].left,r=tree[x].right; tree[x].max=max(tree[l].max,tree[r].max);}void build(int &x,int l,int r){ x=++num;tree[x].l=l;tree[x].r=r;tree[x].left=tree[x].right=tree[x].lazy=0; if(l==r){tree[x].max=w[l];return;} int mid=l+r>>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r); update(x);}inline void pushdown(int x){ if (!tree[x].lazy) return; int l=tree[x].left,r=tree[x].right; tree[l].lazy+=tree[x].lazy;tree[r].lazy+=tree[x].lazy; tree[l].max+=tree[x].lazy;tree[r].max+=tree[x].lazy; tree[x].lazy=0;}void change(int x,int l,int r,int v){ if (l<=tree[x].l&&r>=tree[x].r){tree[x].max+=v;tree[x].lazy+=v;return;} int mid=tree[x].l+tree[x].r>>1;pushdown(x); if (l<=mid) change(tree[x].left,l,r,v); if (r>mid) change(tree[x].right,l,r,v); update(x);}long long query(int x,int l,int r){ if (l<=tree[x].l&&r>=tree[x].r) return tree[x].max; int mid=tree[x].l+tree[x].r>>1;pushdown(x);long long tmp=-inf; if (l<=mid) tmp=max(tmp,query(tree[x].left,l,r)); if (r>mid) tmp=max(tmp,query(tree[x].right,l,r)); return tmp;}int main(){ freopen("hdu5692.in","r",stdin); T=read();int cnt=0; while (T--){ //注意所有编号都已经增加1 printf("Case #%d:\n",++cnt); n=read();m=read();num=0;memset(h,0,sizeof(h));memset(w,0,sizeof(w)); for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。