In this HackerEarth Tree and K-Tuple problem solution You have a Tree with N nodes rooted at 1 where ith node is associated with a value Ai. Now consider the following definition:
K-Tuple: A tuple of K + 1 nodes (X1, X2, X3,..., Xk+1) is a K-Tuple if:
  1.  Xi is an ancestor of Xi+1 for all 1<=i<=K
  2.  Axi > Axi+1 for all 1<=i<=K
Calculate the number of K-Tuples in the tree.


HackerEarth Tree and K-Tuple problem solution


HackerEarth Tree and K-Tuple problem solution.

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define maxn 100005
#define boost ios::sync_with_stdio(false);cin.tie(0)
#define fr freopen("source.txt","r",stdin),freopen("output.txt","w",stdout)
#define SET(a,b) memset(a,b,sizeof(a))

ll a[maxn],sz[maxn],mark[maxn],t[maxn],temp[maxn],ans[maxn];
vector<int>g[maxn];

void update(int pos,ll val){
val=(val+mod)%mod;
for(int i=pos;i<maxn;i+=i&-i){
t[i]+=val;
if(t[i]>=mod)t[i]%=mod;
}
}

ll read(int pos){
ll res=0;
for(int i=pos;i>0;i-=i&-i){
res+=t[i];
if(res>=mod)res-=mod;
}
return res;
}


void pre(int v,int p){
sz[v]=1;
for(int u:g[v]){
if(u-p){
pre(u,v);
sz[v]+=sz[u];
}
}
}

void add(int v,int p){
update(a[v],ans[v]);
for(int u:g[v]){
if(u-p&&mark[u]!=1){
add(u,v);
}
}
}

void rem(int v,int p){
update(a[v],-ans[v]);
for(int u:g[v]){
if(u-p&&mark[u]!=1){
rem(u,v);
}
}
}

void dfs(int v,int p,int keep){
int mx=-1;
int bigchild=-1;
for(int u:g[v]){
if(u-p){
if(mx<sz[u]){
mx=sz[u];
bigchild=u;
}
}
}

for(int u:g[v]){
if(u-p && u!=bigchild){
dfs(u,v,0);
}
}

if(bigchild!=-1){
dfs(bigchild,v,1);
mark[bigchild]=1;
}

add(v,p);
temp[v]=read(a[v]-1);

if(bigchild!=-1){
mark[bigchild]=0;
}

if(keep==0){
rem(v,p);
}
}

int main(){
boost;

int n,k;
cin>>n>>k;

rep(i,1,n)cin>>a[i];

rep(i,2,n){
int u,v;
cin>>u>>v;
g[v].pb(u);
g[u].pb(v);
}

pre(1,0);

rep(i,1,n)ans[i]=1;

rep(i,1,k){
dfs(1,0,0);
rep(j,1,n)ans[j]=temp[j];
}

ll sum=0;
rep(i,1,n)sum=(sum+ans[i])%mod;
cout<<sum;

return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
vector<int>g[100011];
int bt[100011][22];
const int mod = 1e9+7;
void update(int k,int ind,int val) {
while(ind) {
bt[ind][k] += val;
if(bt[ind][k]<0) bt[ind][k]+=mod;
if(bt[ind][k]>=mod) bt[ind][k]-=mod;
ind-=(ind&-ind);
}
}
int query(int k,int ind) {
int ret = 0;
while(ind<=100000) {
ret += bt[ind][k];
if(ret>=mod) ret-=mod;
ind+=(ind&-ind);
}
return ret;
}

int ans = 0;
int N,k;
int dp[100011][22];
int A[100011];
void dfs(int v,int p) {
dp[v][1] = 1;
for(int i=2;i<=k+1;i++) {
dp[v][i] = query(i-1,A[v]+1);
}
for(int i=1;i<=k+1;i++) {
update(i,A[v],dp[v][i]);
}
ans += dp[v][k+1];
if(ans >=mod) ans-=mod;

for(auto x:g[v]) {
if(x!=p) {
dfs(x,v);
}
}
for(int i=1;i<=k+1;i++) {
update(i,A[v],-dp[v][i]);
}
}
int main()
{
int u,v;
cin >> N >> k;
for(int i=1;i<=N;i++) {
cin >> A[i];
}
for(int i=0;i<N-1;i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
cout << ans;
}