Codeforces ラウンド #279 (ディビジョン 2) F. ツリーランド ツアー（lis+dfs）_html/css_WEB-ITnose

質問リンク:

huangjing

質問の意味: 無向非巡回グラフを教えてから、接続する道路上のリスを見つけます。

アイデア: lis を見つけるための点を列挙します。複雑さは n^2logn です。この複雑さは時間に関しては少し謎に見えるため、データは少し弱いと推定されます。 。 。

まずポイントを列挙し、主に dfs を使用して lis を検索します。バックトラッキングのアイデアが使用されます。更新されている限り、操作は保存される必要があり、今回は検索が完了すると、それが実行されます。多くの異なるルートがあるため、g 配列の値をすぐに復元する必要があります。そのため、1 つのルートが完了したら、他のルートへの影響を避けるために前の状態を復元する必要があります。 。たとえ彼らが暴力だと言っているとしても、この質問はとても良い質問だと思います。 。 。

タイトル:

F. ツリーランド ツアー

テストごとの制限時間

テストごとのメモリ制限

入力

出力

「Road Accident」バンドはツリーランド周辺で前例のないツアーを計画しており、RA ファンはそのイベントを楽しみにしており、お気に入りのグループが何回コンサートを行うか賭けています。

ツリーランドは n つの都市で構成されています。 、いくつかの都市のペアは双方向の道路で接続されています。国には全体的に n?-?1 つの道路があり、他の都市からは 1 から n までの整数でアクセスできることがわかります。私たちは、バンドが何らかの道に沿って移動し、その道沿いのいくつかの都市でコンサートを開催することを知っています。その道中、毎回 1 つの都市を 2 回通過するわけではありません。彼らはこれまで訪れたことのない都市に移動します。したがって、ミュージシャンたちは（どの都市も二度訪れることなく）ある道に沿って旅し、途中のいくつかの（必ずしもすべてではない）都市でコンサートを開催します。

ツアー中にすべての大きなスタジアムとコンサートホールを集める予定なので、毎回コンサート都市で以前に訪れた人口よりも人口が多い都市、つまり人口が多い都市の順序で演奏します。コンサートの開催数はますます増えています

「交通事故」バンドのリーダーとの最近のインタビューで、バンドは可能な限り多くの都市でコンサートを行うとファンに約束しました。ツリーランドの都市をチェーン化し、これらの都市のいくつかでコンサートを開催することで、人口が増加し、コンサートの数が可能な限り多くなるでしょう

ツリーランドのファンは、グループが何回コンサートを行うかを必死に把握しようとしています。本物のプログラマーの助けがなければ管理できないようです! ファンがコンサートの数を見つけるのを手伝ってください。

入力の最初の行には整数 n (2?≤) が含まれています。 ?n? ≤?6000) ? 次の行には n 個の整数 r1,?r2,?...,?rn (1?≤?ri?≤?106) が含まれます。次の n?-?1 行には、1 行につき 1 つの道路の説明が含まれます。各道路は、整数 aj、bj (1?≤?aj、?bj?≤?) で定義されます。 n) ? j 番目の道路で接続されている都市の番号のペア。行内のすべての数字はスペースで区切られています。

「交通事故」バンドが発生している都市の数を出力します。コンサートを開催します

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<map>#include<vector>#include<cmath>#include<string>#include<queue>#define eps 1e-9#define ll long long#define INF 0x3f3f3f3fusing namespace std;priority_queue<int,vector<int>,greater<int> >Q;const int maxn=6000+10;struct Egde{    int next,to;}edge[maxn<<1];int g[maxn],val[maxn],head[maxn],cnt,n,ans,top;void add_edge(int x,int y){    edge[++cnt].to=y;    edge[cnt].next=head[x];    head[x]=cnt;}void dfs(int u,int top=0,int fa=0){     int tmp,pos;     if(top==0||val[u]>g[top])     {         pos=++top;         tmp=g[top];         g[top]=val[u];         ans=max(ans,top);     }     else     {         pos=lower_bound(g+1,g+1+top,val[u])-g;         tmp=g[pos];         g[pos]=val[u];     }     for(int i=head[u];~i;i=edge[i].next)     {         int v=edge[i].to;         if(v!=fa)            dfs(v,top,u);     }     g[pos]=tmp;}int main(){    int x,y;    while(~scanf("%d",&n))    {        ans=cnt=0;        memset(head,-1,sizeof(head));        memset(g,-1,sizeof(g));        for(int i=1;i<=n;i++)            scanf("%d",&val[i]);        for(int i=1;i<=n-1;i++)        {            scanf("%d%d",&x,&y);            add_edge(x,y);            add_edge(y,x);        }        for(int i=1;i<=n;i++)            dfs(i);        printf("%d\n",ans);    }    return 0;}