1 #include<cstdio>
 2 #include<algorithm>
 3 #include<queue>
 4 #include<iostream>
 5 using namespace std;
 6 typedef long long ll;
 7 int num[100005];
 8 priority_queue <int,vector<int>,greater<int>  > Q;
 9 int main(){
10     ll b;int n,k;
11     while(cin >> n >> k){
12         cin >>b;
13         for(int i=0;i<n;i++)
14             cin >>num[i];
15         ll sum = 0;
16         int ans = n;
17         n--;
18         while(!Q.empty())Q.pop();
19         for(int i = n-k+1; i<n; i++){
20             if(i < 0) continue;
21             sum += num[i];
22             Q.push(num[i]);
23         }
24         for(int i = n-k;i>=0; i--){
25 //            cout<<sum<<endl;
26             sum+= num[i];
27             Q.push(num[i]);
28 //            cout<<i<<" "<<sum<<endl;
29 //            cout<<Q.top()<<endl;
30             if(sum > b) ans = i+1;
31             if(sum-Q.top() > b) {
32                 ans = 1;
33                 break;
34             }
35             sum -= Q.top();
36             Q.pop();
37         }
38         cout<<ans<<endl;
39     }
40 }
41 

  1 // template
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cassert>
  5 #include<cstdio>
  6 #include<cstdlib>
  7 #include<cstring>
  8 using namespace std;
  9 template <typename T> inline void chkmax(T &a, T b){if(a<b) a=b;}
 10 // graph
 11 const int V = 100005;
 12 const int E = 200005;
 13 int head[V],pnt[E],nxt[E],flag[E];
 14 int n,e;
 15 void addedge(int u,int v){
 16     nxt[e] = head[u];
 17     pnt[e] = v;
 18     head[u] = e;
 19     e ++;
 20 }
 21 // dsu 
 22 int parent[V];
 23 int find(int x){ return x == parent[x] ? x : parent[x] = find(parent[x]);}
 24 // seg_ment tree
 25 int seg[V<<2], M;
 26 void find(int l,int r){
 27     //cout<<l<<" "<<r<<endl;
 28     for(l += M-1, r += M+1; l^r^1; l>>=1, r>>=1){
 29         if(~l&1) seg[l^1]++;
 30         if(r&1) seg[r^1]++;
 31     }
 32 }
 33 // prepare
 34 int deep[V],size[V],heavy[V],P[V];
 35 void dfs(int u,int f){
 36     size[u] = 1;
 37     int mx = 0, s = -1;
 38     for(int i=head[u]; i!=-1;i = nxt[i]){
 39         if( pnt[i] == f) continue;
 40         int v = pnt[i];
 41         P[v] = i^1;
 42         deep[v] = deep[u] + 1;
 43         dfs(v,u);
 44         if(size[v] > mx){
 45             mx = size[v];
 46             s = i;
 47         }
 48         size[u] += size[v];
 49     }
 50     heavy[u] = s;
 51     if(s!=-1) parent[pnt[s]] = u;
 52 }
 53 void prepare(){
 54     for(int i=0;i<n;i++) parent[i] = i;
 55     deep[0] = 0;
 56     P[0] = -1;
 57     dfs(0,0);
 58     for(int i=30;i;i--) if((1<<i) > n+1) M = 1<<i;
 59     for(int i=0;i<2*M;i++) seg[i] = 0;
 60     int len = 1;
 61     for(int u = 0; u<n; u++) if(heavy[u] == -1){
 62         int v = u;
 63         while(v && pnt[heavy[pnt[P[v]]]] == v){
 64             flag[P[v]] = flag[P[v]^1] = len ++;
 65             v = pnt[P[v]];
 66         }
 67     }
 68 }
 69 // operator
 70 int lca(int u,int v){
 71     while(1){
 72         int a = find(u), b = find(v);
 73         if(a == b) return deep[u]<deep[v] ? u : v;
 74         else if(deep[a] > deep[b]) u = pnt[P[a]];
 75         else v = pnt[P[b]];
 76     }
 77 }
 78 int cnt[E];
 79 void query(int u,int v){
 80     //cout<<"query: "<<u<<" "<<v<<endl; 
 81     while(u != v){
 82         int l = P[u];
 83         if(pnt[heavy[pnt[P[u]]]] == u){
 84             int p = find(u);
 85             if(deep[p] < deep[v]) p = v;
 86             int r = heavy[p];
 87             assert(flag[l] <= flag[r]);
 88             find(flag[l],flag[r]);
 89             u = p;
 90         }
 91         else {
 92             u = pnt[l];
 93             cnt[l]++; cnt[l^1]++;
 94 //            cout<<l<<endl;
 95         }
 96     }
 97 }
 98 void ask(int a,int b){
 99     int p = lca(a,b);
100 //    cout<<a<<" "<<b<<" "<<p<<endl;
101     query(a,p); query(b,p);
102 }
103 // main
104 int main(){
105     int k;
106     while(~scanf("%d",&n)){
107         e = 0;
108         memset(head,-1,sizeof(head));
109         memset(cnt,0,sizeof(cnt));
110         for(int i=0;i<n-1;i++){
111             int u,v;
112             scanf("%d%d",&u,&v);
113             u--; v--;
114             addedge(u,v);
115             addedge(v,u);
116         }
117         prepare();
118         cin >>k;
119         while(k--){
120             int u,v;
121             scanf("%d%d",&u,&v);
122             u--;v--;
123             ask(u,v);
124         }
125         for(int i=0;i<e;i+=2){
126             int v = pnt[i], u = pnt[i^1];
127             if(heavy[v]!=(i^1) && heavy[u]!=i){
128                 cout<<cnt[i]<<" ";
129             }
130             else {
131                 int pos = flag[i]+M,ans = 0;
132                 while(pos) {ans += seg[pos]; pos >>=1;}
133                 cout<<ans<<" ";
134             }
135         }
136         cout<<endl;
137     }
138 }
139