The problem is long and has many conditions, so we consider starting with Subtask $$$3$$$ ($$$a_i=1,b_i=i+1$$$ for all $$$i$$$); since all edges have an endpoint of $$$1$$$, the condition $$$w_{AB}\le c_A+c_B$$$ can be transformed into $$$w_{1B}\le c_{1,i}+c_{B,1}\Rightarrow c_{1,i}\ge w_{1B}-c_{B,1}$$$, that is arrange a corresponding $$$c_{1,i}$$$ for each node so that it satisfies this condition. Also since the right hand side of the inequality is a fixed value, consider a greedy algorithm and sort all $$$c_{1,i}$$$ and $$$w_{1B}-c_{B,1}$$$ separately, if $$$c_{1,i}<w_{1B}-c_{B,1}$$$ at the corresponding position then there is no solution; otherwise it is sufficient to arrange a corresponding $$$c_{1,i}$$$ at each node $$$B$$$.

Consider an extension of the above; for a node $$$U$$$ consider all its sons: If all the descendants of a son $$$K$$$ have finished arranging, then it will necessarily be left with a $$$c_{K,i}$$$ (denoted $$$up_K$$$) to upload to the father. Still considering greedy algorithm, sort all the $$$up_K$$$ uploaded from the son by $$$w_{UK}-up_K$$$, and then sort all the $$$c_{U,i}$$$ of node $$$U$$$ to check if the corresponding position satisfies $$$c_{U,i}\ge w_{UK}-up_K$$$. But if there is a corresponding position that is unsatisfied now, it can upload the $$$c_{U,i}$$$ of that position to the father of $$$U$$$, and if there is still an unsatisfied one after that there is no solution; and if there is no such $$$c_{U,i}$$$, then upload the largest $$$c_{U,i}$$$ (i.e., the remaining one) to the father. Clearly such an algorithm is correct. Note the case of the root.

Finally doing a topological sort after determining the order of all edges of each node will determine the global order of the edges.

Time complexity: $$$O(n\log n)$$$.

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
int main(){
  ios::sync_with_stdio(false);
  int n,id; cin>>n>>id;
  vector<tpi> e(n-1);
  vector<vector<tpi> > g(n);
  vector<vector<int> > c(n);
  for(int i=0;i<n-1;i++){
    auto &[u,v,w]=e[i]; cin>>u>>v>>w;
    g[--u].emplace_back(--v,w,i);
    g[v].emplace_back(u,w,i);
  }
  for(int i=0;i<n;i++){
    c[i].resize(g[i].size());
    for(auto &j:c[i])cin>>j;
  }
  for(auto &i:c)reverse(i.begin(),i.end());
  vector<vector<int> > l(n);
  for(int i=0;i<n;i++)
    l[i].resize(c[i].size(),-1);
  vector<int> up(n),ps(n);
  function<void(int,int)> dfs=[&](int u,int f){
    for(auto [i,w,n]:g[u])
      if(i!=f)dfs(i,u);
    vector<pii> s(c[u].size()),o(c[u].size());
    for(int i=0;i<c[u].size();i++)
      o[i]=make_pair(c[u][i],i);
    sort(o.begin(),o.end());
    if(u){
      int p=0,d=0;
      for(auto [i,w,n]:g[u])
        if(i!=f)s[p++]=make_pair(w-up[i],n);
        else s[c[u].size()-1]=make_pair(0,n);
      sort(s.begin(),prev(s.end()));
      for(int i=0;i<c[u].size()-1;i++){
        if(o[i+d].first<s[i].first){
          if(d)cout<<"No\n",exit(0);
          d=1,up[u]=o[i].first,ps[u]=o[i].second;
          if(o[i+d].first<s[i].first)cout<<"No\n",exit(0);
        } // There exists c[u][i] that doesn't satisfy the inequality condition
        l[u][o[i+d].second]=s[i].second;
      }
      if(!d)up[u]=o.back().first,ps[u]=o.back().second;
      l[u][ps[u]]=s.back().second;
    } // Normal nodes
    else{
      for(int i=0;i<c[u].size();i++){
        auto [v,w,n]=g[u][i];
        s[i]=make_pair(w-up[v],n);
      }
      sort(s.begin(),s.end());
      for(int i=0;i<c[u].size();i++){
        if(o[i].first<s[i].first)cout<<"No\n",exit(0);
        l[u][o[i].second]=s[i].second;
      }
    } // Root
  };
  dfs(0,0);
  vector<vector<int> > g2(n-1);
  vector<int> d(n);
  for(int i=0;i<n;i++)
    for(int j=1;j<c[i].size();j++)
      g2[l[i][j-1]].emplace_back(l[i][j]),d[l[i][j]]++;
      // Determine the order of neighboring edges
  queue<int> q;
  for(int i=0;i<n-1;i++)
    if(!d[i])q.emplace(i);
  cout<<"Yes\n";
  while(!q.empty()){
    int u=q.front(); q.pop();
    cout<<u+1<<' ';
    for(int i:g2[u])
      if(!--d[i])q.emplace(i);
  } // Topological sort
  return 0;
}

All arrays mentioned below are $$$0$$$-indexed. The "ordinal" of a gift is referred to as its top to bottom position in the stack, i.e. the ordinal of a gift is independent of which stack it is in.

Let $$$c$$$ be the number of kinds of gifts, and eliminate the $$$c\le t$$$ case, where the answer is $$$1$$$. Next, consider only the $$$c>t$$$ case, where it is easy to see that if a contestant's first gift is in the $$$i(0\le i<k-2)$$$-th heap, the next contestant's first gift won't be in the $$$i+2$$$-th heap.

Consider what strategy for distributing the gifts is optimal: obviously, the more gifts each contestant takes, the better. So for each $$$i(0\le i<n)$$$, if the ordinal of the first gift taken by one contestant is $$$i$$$, then the ordinal of the first gift taken by the next contestant is $$$nx_i$$$ (if its last gift isn't in the same stack as the next contestant's first gift, for convenience, let $$$nx_i\ge n$$$; i.e., if the next contestant's first gift is the $$$j$$$-th in the next stack, then $$$nx_i=n+j$$$). All $$$nx_i$$$ can be simply preprocessed using arrays or std::set.

But this isn't enough. So for each $$$i$$$ consider processing the ordinal $$$f_i$$$ of the first gift for an contestant who takes the first gift with ordinal $$$i$$$, the ordinal number $$$f_i$$$ of the first gift for the first contestant who gets the next gift in the stack from it, and the number of contestants in between $$$d_i$$$. This part can be solved by BFS.

So by making $$$p\leftarrow 0$$$, executing $$$p=nx_{f_p}-n$$$ over and over, and adding $$$d_p$$$, you can pass the $$$k\le 10^6$$$ part, as I did in the contest. The implementation of this part of the code will vary from person to person, e.g. you may need to add $$$k$$$ to the last answer to get the correct answer, etc.

Consider optimizing the above process. We find that $$$p$$$ returns to the same value it had after a number of cycles (this number won't exceed $$$n$$$), and so on. since each $$$p$$$ corresponds to only one $$$nx_{f_p}-n$$$, this is the structure of a pseudotree. So we consider finding a cycle. Specifically, find the cycle of the loop, process the cumulative values of $$$d_p$$$ in the part before the loop and in the last remaining incomplete loop, and quickly compute the cumulative value of $$$d_p$$$ in the middle part of the complete loop to find the answer. You can refer to the code for more details on how to do this.

The $$$O(n\log n)$$$ approach can be implemented more simply (but with the risk of TLE) with std::set and std::map. It is also possible to reduce the time complexity to $$$O(n)$$$ by discretization and hash tables.

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
struct Hash{
  static uint64_t splitmix64(uint64_t x){
    x+=0x9e3779b97f4a7c15;
    x=(x^x>>30)*0xbf58476d1ce4e5b9;
    x=(x^x>>27)*0x94d049bb133111eb;
    return x^x>>31;
  }
  size_t operator()(uint64_t x)const{
    static const uint64_t FIXED_RANDOM=chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x+ FIXED_RANDOM);
  }
};
// Hashing function from https://codeforces.net/blog/entry/62393
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,k,t; long long c=0; cin>>n>>k>>t;
  vector<int> a(n);
  __gnu_pbds::gp_hash_table<int,int,Hash> m;
  for(auto &i:a)
    if(cin>>i;m.find(i)==m.end())m[i]=c++;
  for(auto &i:a)i=m[i]; // Discretization
  if(c<=t)cout<<"1\n",exit(0);
  vector<int> nx(n),d(n),f(n),s(n);
  vector<vector<int> > g(n);
  for(int i=0,l=0,e=0;i<n;i++){
    while(1){
      if(++s[a[l%n]]==1)e++;
      if(e>t){
        nx[i]=l,s[a[l%n]]=0,e--;
        if(l<n)g[l].emplace_back(i);
        break;
      } // The kinds of gifts > t
      l++;
    }
    if(!--s[a[i]])e--;
  } // Find nx[i]
  queue<int> q;
  for(int i=n-1;i>=0;i--)
    if(nx[i]>=n)q.emplace(f[i]=i);
  while(!q.empty()){
    int u=q.front(); q.pop();
    for(int i:g[u])
      f[i]=f[u],d[i]=d[u]+1,q.emplace(i);
  } // Find f[i] and d[i]
  vector<int> w(n<<1),b(n,-1);
  for(int i=c=0,p=0;i<k;i++){
    if(~b[p]){
      int x=(k-b[p])/(i-b[p]),r=(k-b[p])%(i-b[p]);
      c+=(c-w[b[p]]+d[p])*(x-1);
      for(int j=0;j<r;j++)
        c+=d[p],p=nx[f[p]]-n;
      break;
    } // Found the cycle
    w[b[p]=i]=(c+=d[p]),p=nx[f[p]]-n;
  } // Find the cycle on a pseudotree
  cout<<c+k<<endl;
  return 0;
}