1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 typedef long long ll;
  5 struct way{int po,next;} e[200010];
  6 struct node{ll lm,rm,s,mx;} tr[100010*4];
  7 int s[100010],a[100010],b[100010],c[100010],be[100010],d[100010],p[100010],fa[100010];
  8 int n,m,len,t,q;
  9 const ll mi=-1000000000ll*100001ll;
 10 const node inf={mi,mi,0,mi};
 11 void add(int x, int y)
 12 {
 13      e[++len].po=y;
 14      e[len].next=p[x];
 15      p[x]=len;
 16 }
 17 
 18 void dfs1(int x)
 19 {
 20      s[x]=1;
 21      for (int i=p[x]; i; i=e[i].next)
 22      {
 23          int y=e[i].po;
 24          if (fa[x]!=y)
 25          {
 26             fa[y]=x; d[y]=d[x]+1;
 27             dfs1(y);
 28             s[x]+=s[y];
 29          }
 30      }
 31 }
 32 
 33 void dfs2(int x)
 34 {
 35      c[x]=++t;
 36      b[t]=x;
 37      int q=0;
 38      for (int i=p[x]; i; i=e[i].next)
 39      {
 40          int y=e[i].po;
 41          if (c[y]==0&&s[q]<s[y]) q=y;
 42      }
 43      if (q)
 44      {
 45         be[q]=be[x];
 46         dfs2(q);
 47      }
 48      for (int i=p[x]; i; i=e[i].next)
 49      {
 50          int y=e[i].po;
 51          if (fa[x]!=y&&y!=q)
 52          {
 53             be[y]=y;
 54             dfs2(y);
 55          }
 56      }
 57 }
 58 
 59 void update(node &a,node b,node c)
 60 {
 61     a.s=b.s+c.s;
 62     a.lm=max(b.lm,b.s+c.lm);
 63     a.rm=max(c.rm,c.s+b.rm);
 64     a.mx=max(b.rm+c.lm,max(b.mx,c.mx));
 65     a.mx=max(a.mx,max(a.rm,a.lm));
 66 }
 67 
 68 void build(int i,int l,int r)
 69 {
 70     if (l==r) tr[i].mx=tr[i].s=tr[i].lm=tr[i].rm=a[b[l]];
 71     else {
 72         int m=(l+r)>>1;
 73         build(i*2,l,m);
 74         build(i*2+1,m+1,r);
 75         update(tr[i],tr[i*2],tr[i*2+1]);
 76     }
 77 }
 78 
 79 node ask(int i,int l,int r,int x,int y)
 80 {
 81     if (x<=l&&y>=r) return tr[i];
 82     else {
 83         int m=(l+r)>>1;
 84         if (x<=m&&y>m)
 85         {
 86             node s,a=ask(i*2,l,m,x,y),b=ask(i*2+1,m+1,r,x,y);
 87             update(s,a,b);
 88             return s;
 89         }
 90         else if (x<=m) return ask(i*2,l,m,x,y);
 91         else if (y>m) return ask(i*2+1,m+1,r,x,y);
 92     }
 93 }
 94 
 95 ll work(int x,int y)
 96 {
 97     node sx=inf,sy=inf,s;
 98     while (be[x]!=be[y])
 99     {
100           if (d[be[x]]>=d[be[y]])
101           {
102              update(sx,ask(1,1,n,c[be[x]],c[x]),sx);
103              x=fa[be[x]];
104           }
105           else {
106              update(sy,ask(1,1,n,c[be[y]],c[y]),sy);
107              y=fa[be[y]];
108           }
109     }
110     swap(sx.lm,sx.rm);
111     if (c[x]>c[y])
112     {
113         s=ask(1,1,n,c[y],c[x]); swap(s.lm,s.rm);
114         update(sx,sx,s);
115     }
116     else update(sy,ask(1,1,n,c[x],c[y]),sy);
117     update(s,sx,sy);
118     return s.mx;
119 }
120 
121 int main()
122 {
123     scanf("%d",&n);
124     int x,y;
125     for (int i=1; i<n; i++)
126     {
127         scanf("%d%d",&x,&y);
128         add(x,y);
129         add(y,x);
130     }
131     for (int i=1; i<=n; i++) scanf("%d",&a[i]);
132     dfs1(1);
133     t=0; be[1]=1;
134     dfs2(1);
135     build(1,1,n);
136     scanf("%d",&q);
137     for (int i=1; i<=q; i++)
138     {
139         scanf("%d%d",&x,&y);
140         printf("%I64d\n",work(x,y));
141     }
142 }

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 struct node{int lm,rm,mx;} tr[300010*4];
 6 int a[300010],n,q;
 7 ll b[300010];
 8 
 9 int dcmp(ll a)
10 {
11     if (a>0) return 1;
12     if (a<0) return -1;
13     return 0;
14 }
15 
16 void update(int i,int l,int r)
17 {
18     int m=(l+r)>>1;
19     tr[i].mx=max(tr[i*2].mx,tr[i*2+1].mx);
20     if (dcmp(b[m])<=dcmp(b[m+1])) tr[i].mx=max(tr[i].mx,tr[i*2].rm+tr[i*2+1].lm);
21     tr[i].lm=tr[i*2].lm;
22     if (tr[i].lm==m-l+1&&dcmp(b[m])<=dcmp(b[m+1])) tr[i].lm=tr[i].lm+tr[i*2+1].lm;
23     tr[i].rm=tr[i*2+1].rm;
24     if (tr[i].rm==r-m&&dcmp(b[m])<=dcmp(b[m+1])) tr[i].rm=tr[i].rm+tr[i*2].rm;
25 }
26 
27 void build(int i,int l,int r)
28 {
29     if (l==r)
30     {
31         int w=dcmp(b[l])!=0;
32         tr[i]=(node){w,w,w};
33     }
34     else {
35         int m=(l+r)>>1;
36         build(i*2,l,m);
37         build(i*2+1,m+1,r);
38         update(i,l,r);
39     }
40 }
41 
42 void work(int i,int l,int r,int x,int z)
43 {
44     if (l==r)
45     {
46         b[l]+=z;
47         int w=dcmp(b[l])!=0;
48         tr[i]=(node){w,w,w};
49     }
50     else {
51         int m=(l+r)>>1;
52         if (x<=m) work(i*2,l,m,x,z); else work(i*2+1,m+1,r,x,z);
53         update(i,l,r);
54     }
55 }
56 
57 int main()
58 {
59     scanf("%d",&n);
60     for (int i=1; i<=n; i++) scanf("%d",&a[i]);
61     for (int i=1; i<n; i++) b[i]=a[i]-a[i+1];
62     if (n>1) build(1,1,n-1);
63     scanf("%d",&q);
64     for (int i=1; i<=q; i++)
65     {
66         int l,r,z;
67         scanf("%d%d%d",&l,&r,&z);
68         if (n==1) puts("1");
69         else {
70             if (l>1) work(1,1,n-1,l-1,-z);
71             if (r<n) work(1,1,n-1,r,z);
72             printf("%d\n",tr[1].mx+1);
73         }
74 
75     }
76 }

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 struct node{
 6     ll d,a;int id;
 7     friend bool operator <(node a,node b)
 8     {
 9         return a.d<b.d;
10     }
11 } a[50],c[(1<<21)+5];
12 int t,n1,n2,n,s1,s2,b,mi[(1<<21)+5],w[50];
13 ll ans;
14 const ll inf=9223372036854775807ll;
15 
16 void pdf(int i,int st, ll sd, ll sa)
17 {
18     if (i==n1+1)
19     {
20         c[++t]=(node){sd,sa,st};
21         if (sd>=b&&ans>sa)
22         {
23             ans=sa;
24             s1=st; s2=0;
25         }
26         return;
27     }
28     pdf(i+1,st,sd,sa);
29     if (sd+1>=a[i].d) pdf(i+1,st|(1<<(i-1)),sd+a[i].d,sa+a[i].a);
30 }
31 
32 void dfs(int i,int st,ll sd,ll sa,ll key)
33 {
34     if (i==n2+1)
35     {
36         node x=(node){max(key,b-sd),0,0};
37         int pos=lower_bound(c+1,c+1+t,x)-c;
38         if (pos==t+1) return;
39         if (c[mi[pos]].a+sa<ans)
40         {
41             s1=c[mi[pos]].id; s2=st;
42             ans=c[mi[pos]].a+sa;
43         }
44         return;
45     }
46     dfs(i+1,st,sd,sa,key);
47     dfs(i+1,st|(1<<(i-1)),sd+a[n1+i].d,sa+a[n1+i].a,max(key,a[i+n1].d-sd-1));
48 }
49 
50 int main()
51 {
52     scanf("%d%d",&n,&b);
53     for (int i=1; i<=n; i++)
54     {
55         int x,y;
56         scanf("%d%d",&x,&y);
57         a[i]=(node){x,y,i};
58     }
59     sort(a+1,a+1+n);
60     ans=inf,s1=0,s2=0;
61     n1=n/2+(n%2),n2=n-n1,t=0;
62     pdf(1,0,0,0);
63     sort(c+1,c+1+t);
64     mi[t]=t;
65     for (int i=t-1; i; i--)
66       mi[i]=c[mi[i+1]].a>=c[i].a?i:mi[i+1];
67     dfs(1,0,0,0,0);
68     if (ans<inf)
69     {
70         int s=0;
71         for (int i=0; i<n1; i++)
72             if (s1&(1<<i)) w[++s]=a[i+1].id;
73         for (int i=0; i<n2; i++)
74             if (s2&(1<<i)) w[++s]=a[i+n1+1].id;
75         printf("%d\n",s);
76         for (int i=1; i<=s; i++)
77         {
78             printf("%d",w[i]);
79             if (i<s) printf(" "); else puts("");
80         }
81     }
82     else puts("-1");
83 }