One important idea of this problem is to use "centroid" of tree.
If you have centroid c, you have some subtree which connects to c, and let the size s₁, s₂, ..., s_k. Now you have 2s_k ≤ n.
First, visit vertex c. Then, visit any vertex (I don't have a proof, but I selected farthest vertex among which I can choose) of which s_i is maximum among subtree i is not most recently visited. Then decrement s_i.
I did this thinking and got passed. Anyway, it was an interesting problem :)

Someone please help with the solution of Div 2 1000?

The problem with the recurrence is that it double counts some configurations, i.e, you'll fail in a case where s = [1], f = [10] (the answer is 2, but I believe this dp will give you something like 11 or something).

To solve this, it requires some observations. First, given a set of intervals, how do you determine if Hero can do them all?

You can do the following greedy algorithm: Sort all the endpoints by finish time (breaking ties arbitrarily). Then, for each interval in order, assign it the earliest available time. The proof is by exchange argument, you can try yourself.

Now, you can apply this idea to a dp approach to count. First, sort all the intervals in order by finish time and add them in one by one. Then, your dp transition is very similar, but you need to break your loop once you find something where j&2^k! = 0. The reason you break is that you are basically simulating the greedy algorithm above. There are some solutions in the practice room if you'd like to look at an implementation.

It's rated without ANY issue, and my rating changed from 2083 to 2143. Also, you can check rating change of all contestants from https://community.topcoder.com/stat?c=round_stats&rd=17048&dn=1 .

You need to sort the queries by cost and run Kuhn's algorithm. One part of the graph is queries, it's very big, the other one is points in time, it has only X = 2000 vertices. Store all unused points in time in set. When you run dfs, you need to find any unused point on a segment, you can do it with lower_bound. This way, each run of dfs will work in , so overall complexity will be , which is still bad. To fix that, only clear used vertices when you actually find augmenting path. This way all runs of dfs together until we increase the matching will take time and we increase the matching only O(X) time so complexity will be .

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

const int mod = (int) 1e9 + 7;
const int maxn = (int) 2e6 + 5;
const int maxx = 2005;
int X[3 * maxn];
int sl[maxn], sr[maxn], c[maxn];
pair<int, int> tosort[maxn];
int p[maxx];
set<int> st;

bool dfs(int v) {
  while (true) {
    auto it = st.lower_bound(sl[v]);
    if (it == st.end() || *it >= sr[v]) {
      break;
    }
    int u = *it;
    st.erase(it);
    if (p[u] == -1 || dfs(p[u])) {
      p[u] = v;
      return true;
    }
  }
  return false;
}

struct HeroicSchedule {
  int getmax(int n, int A, int B, int C, int modStart, int modLen, int modCost) {
    X[0] = A;
    for (int i = 1; i < 3 * n; i++) {
      X[i] = ((long long) X[i - 1] * B + C) % mod;
    }
    for (int i = 0; i < n; i++) {
      sl[i] = X[3 * i] % modStart;
      sr[i] = sl[i] + (X[3 * i + 1] % modLen) + 1;
      c[i] = X[3 * i + 2] % modCost;
    }
    for (int i = 0; i < n; i++) {
      tosort[i] = make_pair(c[i], i);
    }
    sort(tosort, tosort + n, greater< pair<int, int> >());
    st.clear();
    for (int i = 0; i < maxx; i++) {
      p[i] = -1;
      st.insert(i);
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      int v = tosort[i].second;
      if (dfs(v)) {
        res += c[v];
        for (int i = 0; i < maxx; i++) {
          st.insert(i);
        }
      }
    }
    return res;
  }
};

Alternative solution (solution in practice room — I had a small bug in the contest):

A test of tasks can be assigned to days if and only if, for every time interval [L, R), at most R-L tasks are chosen that fit entirely within that interval. Now work through tasks in decreasing order of cost and try to add each, checking the condition each time.

Naively that's O(m³n), but it can be sped up. Firstly, for each L, keep track of the largest R such that the interval [L, R) has zero slack; call this S. Let T[i] = min{S[j] | 0 <= j <= i}. Then a new task [a, b) can be added iff b > T[a]. We can update S and then T after each new task is added, which allows tasks to be rejected in O(1).

We still need to be update to update S efficiently. For each [L, R), let X_LR be the slack in the interval [L, R). For each L, maintain a segment tree with all X_LR. The segment tree needs to be able to support range addition, and a query of the minimum value and the rightmost position of that minimum value (in fact the global minimum will always be zero since X_LL = 0, but phrasing it this way makes it practical to implement as a segment tree).

This gives run-time , assuming a bucket sort for the costs.