## Thursday, November 27, 2014

### Treeland Tour (Codeforces Round #279 Div. 2 Problem F)

Problem Statement:
Codeforces Round #279 Div. 2
Problem F. Treeland Tour

Solution:
The editorial for this round is already up and quite clearly written :)

I think this problem is pretty tedious to get right.. The dynamic programming idea is as follows:
- the "state" of our DP table will be the edges. Pretty interesting.
- Let M(u,v) be the maximum number of concerts if the path ends with edge (u,v). Also, we want vertex v to be where the last concert is held.
- M(u,v) can be calculated by traversing down the tree rooted at u. We traverse down the children of u which does not start with v.
- In each subtree, as we traverse down using DFS, we find an edge (x, y) such that r[y] is less than that of r[v]. Then we update M(u,v) = max(M(u,v), M(x,y)).
- Don't forget to take care of leaves.

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

int dp[6003][6003]; //dp(u,v) = number of concerts ending with edge u,v
int val[6003];
int N;

int dfs(int,int,int);
int compute(int,int);

int dfs(int v, int w, int u){
int ret = (val[v] > val[w] ? 1 : 0);
if(val[v] > val[u]){
ret = max(ret, compute(w,u));
}
int x;
if(x == u) continue;
ret = max(ret, dfs(v, x, w));
}
return ret;
}

int compute(int u, int v){
if(dp[u][v] != -1) return dp[u][v];
int ret = 1;
int w;
if(w == v) continue;
ret = max(ret, dfs(v, w, u) + 1);
}
if(adj[u].size() == 1 && val[v] > val[u]) ret = 2;
dp[u][v] = ret;
return ret;
}

void solve(){
int ans = 0;
for(int i=0;i<=N;++i){
for(int j=0;j<=N;++j){
dp[i][j] = -1;
}
}
for(int i=1;i<=N;++i){
}
}
printf("%d\n", ans);
}

int main(){
int u,v;
scanf("%d", &N);
for(int i=1;i<=N;++i){
scanf("%d", &val[i]);
}