青岛网站设计公司推荐,wordpress首页添加一个超链接框,网站服务器地址怎么查,青岛网站设计软件Problem - E - Codeforces 思路#xff1a;我们考虑用树形dp#xff0c;用f[i][0]表示以i为根#xff0c;并且当前节点不在最长上升子序列中#xff0c;用f[i][1]表示以i为根#xff0c;当前节点在最长上升子序列中#xff0c;那么f[i][0]max(f[j][0],f[j][1])#xff0…Problem - E - Codeforces 思路我们考虑用树形dp用f[i][0]表示以i为根并且当前节点不在最长上升子序列中用f[i][1]表示以i为根当前节点在最长上升子序列中那么f[i][0]max(f[j][0],f[j][1])因为对于以i为根的子树来说i的所有子节点组成的子树是没有关联的所以不包含当前节点的最长上升子序列就是每个子节点的最长上升子序列的和f[i][1]max(f[i][1],f[j][1]1)如果包含当前节点因为我一定是在删除了所有的子节点之后才删除当前节点所以我这个节点的值一定是子节点中除1之外的最小的值并且它只有其中的某一个子节点能够等于这个值那么我们为了让它最大肯定是挑路径最长的那个子节点的值等于这个值这样就能够让f[i][1]最大所以f[i][1]只需要找以i为根的最长的路径就可以
// Problem: E. Hanging Hearts
// Contest: Codeforces - Codeforces Round 831 (Div. 1 Div. 2)
// URL: https://codeforces.com/problemset/problem/1740/E
// Memory Limit: 256 MB
// Time Limit: 1000 ms#includeiostream
#includecstring
#includestring
#includesstream
#includebitset
#includedeque
#includecmath
#includecstdio
#includealgorithm
#includecassert
#includequeue
#includemap
#includestack
#includevector
#includeset
#includecstdlib
#define fi first
#define se second
#define i128 __int128
using namespace std;
typedef long long ll;
typedef double db;
typedef pairint,int PII;
typedef pairint,pairint,int PIII;
const double eps1e-7;
const int N5e57 ,M5e57, INF0x3f3f3f3f,mod1e97,mod1998244353;
const long long int llINF0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x0,f1;char cgetchar();while(c0||c9) {if(c-) f-1;cgetchar();}
while(c0c9) {x(ll)x*10c-0;cgetchar();} return x*f;}
inline void write(ll x) {if(x 0) {putchar(-); x -x;}if(x 10) write(x / 10);putchar(x % 10 0);}
inline void write(ll x,char ch) {write(x);putchar(ch);}
void stin() {freopen(in_put.txt,r,stdin);freopen(my_out_put.txt,w,stdout);}
bool cmp0(int a,int b) {return ab;}
templatetypename T T gcd(T a,T b) {return b0?a:gcd(b,a%b);}
templatetypename T T lcm(T a,T b) {return a*b/gcd(a,b);}
void hack() {printf(\n----------------------------------\n);}int T,hackT;
int n,m,k;
vectorint h[N];
int f[N][2];void dfs(int u,int fa) {f[u][1]1;for(int i0;ih[u].size();i) {int jh[u][i];if(jfa) continue;dfs(j,u);f[u][0]max(f[j][0],f[j][1]);f[u][1]max(f[u][1],f[j][1]1);}
}void solve() {nread();for(int i2;in;i) {int cread();h[c].push_back(i);h[i].push_back(c);}dfs(1,-1);printf(%d\n,max(f[1][0],f[1][1]));
} int main() {// init();// stin();//ios::sync_with_stdio(false); // scanf(%d,T);T1; while(T--) hackT,solve();return 0;
}
