第四题

5 3
1 2
1 3
1 4
1 5
1
2
3

YES
NO
NO

代码如下：

var
        jl,s,g,a,f,x,y:array[1..400000] of longint;
        n,m,dian,i,p,ji,max,max2,jis,ans:longint;
        h:array[1..400000,1..100] of longint;
        bz,zhi:array[1..400000] of boolean;
        bo:boolean;
procedure dg(k:longint);
var
        i,p:longint;
begin
        if k=12 then
          k:=k;
        for i:=1 to g[k] do
          begin
            p:=h[k,i];
            if bz[p]=false then
              begin
                bz[p]:=true;
                dg(p);
                f[k]:=f[k]+f[p];
              end;
          end;
        f[k]:=f[k]+1;
end;
procedure dg2(k:longint);
var
        i,p,t,s:longint;
begin
        s:=n-f[k];
        if bo then
          exit;
        dec(s);
        for i:=1 to g[k] do
          begin
            p:=h[k,i];
            if bz[p] then
              continue;
            if s<f[p] then
              s:=f[p];
          end;
        if s<=n div 2 then
          begin
            bo:=true;
            dian:=k;
            exit;
          end
        else
          begin
            for i:=1 to g[k] do
              begin
                if bz[h[k,i]] then
                  continue;
                bz[h[k,i]]:=true;
                dg2(h[k,i]);
                if bo then
                  exit;
              end;
          end;
end;
procedure jilu(k:longint);
var
        i,p:longint;
begin
        zhi[k]:=true;
        for i:=1 to g[k] do
          begin
            p:=h[k,i];
            if bz[p]=false then
              begin
                bz[p]:=true;
                jilu(p);
              end;
          end;
end;
begin
        assign(input,'h3.in');
        assign(output,'h3.out');
        reset(input);
        rewrite(output);
        read(n,m);
        for i:=1 to n-1  do
          begin
            read(x[i],y[i]);
            inc(g[x[i]]);
            h[x[i],g[x[i]]]:=y[i];
            inc(g[y[i]]);
            h[y[i],g[y[i]]]:=x[i];
          end;
        for i:=1 to m do
          read(a[i]);
        fillchar(bz,sizeof(bz),false);
        fillchar(f,sizeof(f),0);
        bz[x[1]]:=true;
        dg(x[1]);
        fillchar(bz,sizeof(bz),false);    
        bo:=false;
        bz[x[1]]:=true;
        dg2(x[1]);
        fillchar(f,sizeof(f),0);
        fillchar(bz,sizeof(bz),false);
        bz[dian]:=true;
        dg(dian);
        for i:=1 to g[dian] do
          begin
            p:=h[dian,i];
            if max<f[p] then
              begin
                max:=f[p];
                ji:=p;
                jis:=i;
              end;
          end;
        fillchar(bz,sizeof(bz),false);
        fillchar(zhi,sizeof(zhi),false);
        bz[dian]:=true;
        bz[ji]:=true;
        ans:=1;
        jilu(ji);
        for i:=1 to g[dian] do
          if i<>jis then
            begin
              p:=h[dian,i];
              if max2<f[p] then
                max2:=f[p];
            end;

        for i:=1 to m do
          begin
            if a[i]=dian then
              begin
                writeln('YES');
                continue;
              end;
            if (zhi[a[i]]) then
              begin
                if n-f[a[i]]-max2<=n div 2 then
                  writeln('YES')
                else
                  writeln('NO');
              end
            else
              begin
                if n-f[a[i]]-max<=n div 2 then
                  writeln('YES')
                else
                  writeln('NO');
              end;
          end;
        close(input);
        close(output);
end.

最后

以上就是单身心情为你收集整理的第四题的全部内容，希望文章能够帮你解决第四题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。