题意：略。
思路：这是个删边的博弈游戏。
关于删边游戏的预备知识：http://blog.csdn.net/acm_cxlove/article/details/7854532
学习完预备知识后，这一题就不难了。
首先，用tarjan算法找到每棵树中的双连通分量(即树枝上的多边形)，根据Fusion Principle，如果多边形有奇数条边，可以简化为1条边，如果有偶数条边，则可以简化为1个点。代码中使用了vis数组，对于前者，使环内所有的点（包括悬挂点）的vis值为1，后面计算sg值时便不会再进行遍历这些点；对于后者，除了悬挂点和多边形内与悬挂点相邻的一点（相邻点中只取一个）外，多边形内其他点vis为1，这样就相当于将环化为了1条边。另外，题目当中会有重边，根据题意，当出现这种情况时，一定也是出现在树枝的末端。这里直接当作多边形来处理，方法是相同的，如果有偶数条边，化为1个点，奇数条边化为1条边。
然后由Colon Principle，可以计算出整棵树的sg值，之后对于所有的树，就是个Nim游戏了。
更多细节看代码
#include<stdio.h>
#include<string.h>
#include<stack>
#include<algorithm>
#define maxn 105
#define maxp 2000
using namespace std;
int map[maxn][maxn];
bool vis[maxn];
struct node
{
int v, next;
}edge[maxp];
int num_edge, head[maxn];
void init()
{
num_edge = ;
memset(head, -, sizeof(head));
}
void addedge(int a,int b)
{
edge[num_edge].v = b;
edge[num_edge].next = head[a];
head[a] = num_edge++;
}
struct scc
{
int dfn[maxn], low[maxn];
int cnt, scnt;
bool instack[maxn];
stack<int> s;
void init()
{
cnt = scnt = ;
memset(dfn, -, sizeof(dfn));
memset(instack, , sizeof(instack));
}
void tarjan(int u,int father)
{
dfn[u] = low[u] = ++cnt;
s.push(u);
instack[u] = ;
for (int i = head[u]; i != -; i = edge[i].next)
{
int v = edge[i].v;
if (v == father)
{
if (map[u][v] > && map[u][v] % == )
vis[u] = ;
continue;
}
if (dfn[v] == -)
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else if (instack[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
scnt = ;
int last;
for (;;)
{
int temv = s.top();
s.pop();
scnt++;
instack[temv] = ;
if ((temv == u) || s.empty())
break;
vis[temv] = ;
last = temv;
}
if (scnt & )
vis[last] = ;
}
return;
}
void solve(int n)
{
init();
for (int i = ; i <= n; i++) if (dfn[i] == -)
tarjan(i, -);
}
};
int getsg(int u,int father)
{
int osum = ;
for (int i = head[u]; i != -; i = edge[i].next)
{
int v = edge[i].v;
if (!vis[v] && v != father)
osum ^= ( + getsg(v, u));
}
return osum;
}
int main()
{
int k, n, m;
scc g;
while (~scanf("%d", &n))
{
int osum = ;
for (int i = ; i <= n; i++)
{
scanf("%d%d", &m, &k);
int a, b;
init();
memset(map, , sizeof(map));
memset(vis, , sizeof(vis));
while (k--)
{
scanf("%d%d", &a, &b);
addedge(a, b);
map[a][b]++;
addedge(b, a);
map[b][a]++;
}
g.solve(m);
osum ^= getsg(, -);
}
if (osum) printf("Sally\n");
else printf("Harry\n");
}
return ;
}