题目链接：https://vjudge.net/contest/154238#overview。
ABCDE都是水题。
F题，一开始分类讨论，结果似乎写挫了，WA了一发。果断换并查集上，A了。
G题，状态压缩DP，不难写，但是时限有点紧，读入也比较恶心。。值得注意的是计算一个数二进制下有几个1可以用__builtin_popcount(mask)；判断a和b在二进制表示下a是不是b的子集可以用(a&b)==a；另外字符串s想移除最后一位可以s.resize(s.size()-1)或者s.erase(s.end()-1)。
H题，tarjan题，思路不难。无向图缩点以后找一下树的直径，再遍历一下即可。但是被两个傻逼错误卡了好久。。好弱啊。。顺便注意下，无向图的缩点需要在tarjan的时候加一个参数fa，或者用head数组实现邻接表。后者因为反向边和原边的编号是相邻的，可以直接用vis数组来使得反向边不访问，这个方法的好处是可以处理重边，而第一个方法不行。具体的代码实现我之前的模板里有。。贴一下这题的代码好了：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <vector> 5 #include <map> 6 #include <set> 7 #include <queue> 8 #include <iostream> 9 #include <stdlib.h> 10 #include <string> 11 #include <stack> 12 using namespace std; 13 const int inf = 0x3f3f3f3f; 14 typedef long long ll; 15 typedef pair<int,int> pii; 16 const int N = 100000 + 5; 17 18 int n,m,dfs_clock,dfn[N],low[N]; 19 int belong[N],scc_cnt,id[N]; 20 stack<int> S; 21 struct edge 22 { 23 int v,w,nxt; 24 }G[N*8]; 25 int head[N],head2[N],etot; 26 vector<int> bcc[N]; 27 void addEdge(int u,int v,int w,int* head) 28 { 29 G[etot] = (edge){v,w,head[u]}; 30 head[u] = etot++; 31 } 32 33 int pos = 0; 34 void init() 35 { 36 etot = 0; 37 memset(head,-1,sizeof head); 38 memset(head2,-1,sizeof head2); 39 dfs_clock = 0; 40 memset(dfn,0,sizeof(dfn)); 41 memset(belong,0,sizeof(belong)); 42 scc_cnt = 0; 43 memset(id,-1,sizeof(id)); 44 } 45 46 void tarjan(int u,int fa) 47 { 48 dfn[u]=low[u]=++dfs_clock; 49 S.push(u); 50 for(int i=head[u];i!=-1;i=G[i].nxt) 51 { 52 edge e = G[i]; 53 int v = e.v; 54 if(!dfn[v]) 55 { 56 tarjan(v,u); 57 low[u]=min(low[u],low[v]); 58 } 59 else if(dfn[v] < dfn[u] && v != fa) 60 { 61 low[u]=min(low[u],dfn[v]); 62 } 63 } 64 if(low[u]==dfn[u]) 65 { 66 scc_cnt++; 67 bcc[scc_cnt].clear(); 68 for(;;) 69 { 70 int x = S.top();S.pop(); 71 belong[x] = scc_cnt; 72 bcc[scc_cnt].push_back(x); 73 if(id[scc_cnt] == -1 || id[scc_cnt] > x) id[scc_cnt] = x; 74 if(x==u) break; 75 } 76 } 77 78 } 79 80 ll d[N],d1[N],d2[N]; 81 void dfs(int u,int fa,ll* dis) 82 { 83 for(int i=head2[u];i!=-1;i=G[i].nxt) 84 { 85 edge e = G[i]; 86 int v = e.v, w = e.w; 87 if(v == fa) continue; 88 dis[v] = dis[u] + w; 89 dfs(v,u,dis); 90 } 91 } 92 93 void solve() 94 { 95 for(int i=1;i<=n;i++) 96 { 97 if(!dfn[i]) tarjan(i,-1); 98 } 99 100 for(int i=1;i<=n;i++) 101 { 102 int u = belong[i]; 103 for(int j=head[i];j!=-1;j=G[j].nxt) 104 { 105 edge e = G[j]; 106 int v = belong[e.v], w = e.w; 107 if(u != v) 108 { 109 addEdge(u,v,w,head2); 110 } 111 } 112 } 113 114 int x = belong[1]; 115 d[x] = 0; 116 dfs(x,-1,d); 117 int y = x; 118 for(int i=1;i<=scc_cnt;i++) 119 { 120 if(d[i] > d[y]) 121 { 122 y = i; 123 } 124 } 125 d1[y] = 0; 126 dfs(y,-1,d1); 127 x = y; 128 for(int i=1;i<=scc_cnt;i++) 129 { 130 if(d1[i] > d1[x]) 131 { 132 x = i; 133 } 134 } 135 d2[x] = 0; 136 dfs(x,-1,d2); 137 int ans_id = min(id[x],id[y]); 138 ll len = d1[belong[ans_id]] + d2[belong[ans_id]]; 139 for(int i=1;i<=scc_cnt;i++) 140 { 141 ll temp = max(d1[i], d2[i]); 142 if(temp < len) 143 { 144 ans_id = id[i]; 145 len = temp; 146 } 147 else if(temp == len && id[i] < ans_id) ans_id = id[i]; 148 } 149 printf("%d %I64d ",ans_id,len); 150 } 151 152 int main() 153 { 154 int T; 155 scanf("%d",&T); 156 for(int kase=1;kase<=T;kase++) 157 { 158 init(); 159 scanf("%d%d",&n,&m); 160 for(int i=1;i<=m;i++) 161 { 162 int u,v,w; 163 scanf("%d%d%d",&u,&v,&w); 164 addEdge(u,v,w,head); 165 addEdge(v,u,w,head); 166 } 167 solve(); 168 } 169 }