当前位置：首页 > news >正文

男神的补习

news 来源：原创 2024/4/28 18:00:15

男神的补习

题目链接：http://acm.xidian.edu.cn/problem.php?id=1162

DFS序维护线段树

直接拿之前百度之星那题（http://www.cnblogs.com/barrier/p/5831927.html）改一下就过了

代码如下：

 1 #include<cstdio>
 2 #include<vector>
 3 #define LL long long
 4 #define N 100100
 5 #define lson (x<<1)
 6 #define rson (x<<1|1)
 7 #define mid ((l+r)>>1)
 8 using namespace std;
 9 struct node{
10     int sum,lazy;
11 }a[N<<2];
12 int val[N],fa[N],hx[N],L[N],R[N];
13 int idx,n,m,k,root=1,x,y,times,t;
14 bool vis[N];
15 vector<int>e[N];
16 void dfs(int num){
17     vis[num]=1;
18     L[num]=++idx;
19     for(LL i=0;i<e[num].size();i++)
20         if(!vis[e[num][i]])dfs(e[num][i]);
21     hx[L[num]]=num;
22     R[num]=idx;
23 }
24 void push_up(int x){
25     a[x].sum=min(a[lson].sum,a[rson].sum);
26 }
27 void push_down(int x){
28     a[lson].sum+=a[x].lazy,a[lson].lazy+=a[x].lazy;
29     a[rson].sum+=a[x].lazy,a[rson].lazy+=a[x].lazy;
30     a[x].lazy=0;
31 }
32 void build(int x,int l,int r){
33     if(l==r){
34         a[x].sum=val[hx[l]];
35         return;
36     }
37     build(lson,l,mid);
38     build(rson,mid+1,r);
39     push_up(x);
40 }
41 void init(){
42     scanf("%d%d%d",&n,&m,&k);
43     for(int i=1;i<n;++i){
44         scanf("%d%d",&x,&y);
45         e[x].push_back(y);fa[y]=x;
46     }
47     while(fa[root]!=0)root=fa[root];
48     for(int i=1;i<=n;++i)scanf("%d",&val[i]);
49     dfs(root);
50     build(1,1,n);
51 }
52 void add(int x,int l,int r,int cl,int cr,LL v){
53     if(cl<=l&&r<=cr){
54         a[x].sum+=v,a[x].lazy+=v;
55         return;
56     }
57     if(a[x].lazy!=0)push_down(x);
58     if(cl<=mid)add(lson,l,mid,cl,cr,v);
59     if(mid<cr)add(rson,mid+1,r,cl,cr,v);
60     push_up(x);
61 }
62 LL query(int x,int l,int r,int ql,int qr){
63     if(ql<=l&&r<=qr)return a[x].sum;
64     if(a[x].lazy!=0)push_down(x);
65     LL temp=1000000000;
66     if(ql<=mid)temp=min(temp,query(lson,l,mid,ql,qr));
67     if(mid<qr)temp=min(temp,query(rson,mid+1,r,ql,qr));
68     return temp;
69 }
70 int main(void){
71     init();
72     for(;query(1,1,n,L[root],R[root])<60&&times<m;){
73         scanf("%d",&t);
74         add(1,1,n,L[t],R[t],k);
75         ++times;
76     }
77     if(query(1,1,n,L[root],R[root])>=60)printf("%d\n",times);
78     else printf("mdzz\n");
79 }