loj 1412(ツリー上の最長直径の応用)

タイトルリンク:http://lightoj.com/volume_showproblem.php?problem=1412
構想:久しぶりに問題解を書いて、ちょっと手慣れて、この問題は昨日の夜からwaが今までやっと過ぎました...考えは実は簡単で、1枚1枚の最長直径を前処理して、それから尋ねるたびに直接調べることができます.

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<cstring>

 4 #include<algorithm>

 5 #include<vector>

 6 using namespace std;

 7 

 8 const int MAXN = (100000 + 100);

 9 typedef pair<int,int>Pair;

10 

11 vector<int >g[MAXN];

12 vector<Pair >blocks;

13 int n,m,q,len,_count,max_len;

14 bool mark[MAXN];

15 

16 int dfs(int u,int father)

17 {

18     if(!mark[u])mark[u] = true, _count ++;

19     int first = 0, second = 0;

20     for(int i = 0; i < (int)g[u].size(); i ++) {

21         int v = g[u][i];

22         if(v == father)continue;

23         int tmp = dfs(g[u][i],u) + 1;

24         if(tmp > first)second = first, first = tmp;

25         else if(tmp > second)second = tmp;

26     }

27     if(first + second > len)len = first + second;

28     return first;

29 }

30 

31 int cmp(Pair p, Pair q)

32 {

33     if(p.second != q.second){

34         return p.second > q.second;

35     }else

36         return p.first > q.first;

37 }

38 

39 int main()

40 {

41     int u,v,_case,t=1;

42     scanf("%d",&_case);

43     while(_case--){

44         scanf("%d%d",&n,&m);

45         for(int i=0;i<=n;i++)g[i].clear();

46         while(m--){

47             scanf("%d%d",&u,&v);

48             g[u].push_back(v);

49             g[v].push_back(u);

50         }

51         len=0;

52         max_len = 0;

53         memset(mark,false,sizeof(mark));

54         blocks.clear();

55         for(int i=1;i<=n;i++){

56             if(!mark[i]){

57                 len=0;

58                 _count = 0;

59                 dfs(i,-1);

60                 blocks.push_back(make_pair(len,_count));

61                 max_len = max(max_len,len);

62             }

63         }

64         sort(blocks.begin(),blocks.end(),cmp);

65         scanf("%d",&q);

66         printf("Case %d:
",t++);

67         while(q--){

68             int k;

69             scanf("%d",&k);

70             if(k > blocks[0].second){

71                 puts("impossible");

72             }else if(k <= max_len + 1){

73                 printf("%d
",k - 1);

74             }else {

75                 int ans = (1 << 30);

76                 for(int i=0; i<(int)blocks.size(); i++){

77                     if(k > blocks[i].second)break;

78                     ans = min (ans, (blocks[i].first)+2*(k-blocks[i].first-1));

79                 }

80                 printf("%d
",ans);

81             }

82         }

83                             

84     }

85     return 0;

86 }

87 

88 

89                 

90 

91         

92             

93 

94 

95         

96 

97         

View Code