# 某岛

… : "…アッカリ～ン . .. . " .. .
January 27, 2013

# SPOJ 1482. A short vacation in Disneyland

。。树的路径覆盖。

### Analysis:

```const int N = 10009;

int hd[N], suc[N*2], to[N*2], deg[N]; VI adj[N];
int f0[N], f1[N], p0[N], p1[N]; bool vis[N];
int n;

#define v to[i]
void dfs(int p = 0, int u = 1){

REP_G(i, u) if (v != p){
dfs(u, v), f0[u] += f0[v];
}

if (!f0[u]){ // is leaf .. .
f0[u] = f1[u] = 1;
}
else {
f1[u] = f0[u];

int t1 = INF; REP_G(i, u) if (v != p){
if (f1[v] - f1[v] < t1){
t1 = f1[v] - f0[v];
p1[u] = v;
}
}

int t0 = INF; REP_G(i, u) if (v != p && v != p1[u]){
if (f1[v] - f1[v] < t0){
t0 = f1[v] - f0[v];
p0[u] = v;
}
}
f1[u] += t1, f0[u] += t0 + t1 - 1;
checkMin(f0[u], f1[u]);
}
}

void gao(int u = 1, bool flag = false){ // 是否允许分岔。

vis[u] = true;

if (p0[u] && !flag){
gao(p0[u], 1);
}

if (p1[u]){
gao(p1[u], 1);
}

REP_G(i, u) if (!vis[v]) gao(v) ;
}

#undef v
#define v (*it)
void out(int u){
vis[u] = true; ECH(it, adj[u]) if (!vis[v]){
printf(" %d" , v);
out(v) ;
}
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

#define a to[i^1]
#define b to[i]

Rush{

RST(hd, f0, f1, p0, p1);

FOR_C(i, 2, RD(n)<<1){
RD(a, b);
suc[i] = hd[a], hd[a] = i++;
suc[i] = hd[a], hd[a] = i;
}

dfs(); OT(f0[1]);

RST(vis); gao(); RST(vis); REP_1(u, n) if (!vis[u] && SZ(adj[u]) <= 1){
printf("%d", u); out(u);
puts("");
}
}
}
```
```const int N = 10009;

int hd[N], suc[N*2], to[N*2], deg[N];
bool vis[N];
int n;

#define v to[i]

VVI path; VI cur;

void gao(int u){
vis[u] = true; cur.PB(u);
REP_G(i, u) if (!vis[v]) gao(v);
}

void dfs(int p = 0, int u = 1){

//cout << " " << u << endl;

REP_G(i, u) if (v != p){
dfs(u, v);
}

//cout << u << " " << deg[u] << endl;

if (deg[u] <= 1 && p) ++deg[p];
else {
int c = 0; CLR(cur); vis[u] = true;
REP_G(i, u) if (v != p && deg[v] <= 1){

/*cout << "--" << u << " " << v << endl;
cout << "--"; REP(i, SZ(cur)) cout << cur[i] << " ";
cout << endl;*/

if (!c) gao(v), reverse(ALL(cur)), cur.PB(u);
else if (c == 1) gao(v);
else{
if (SZ(cur)) path.PB(cur), CLR(cur);
gao(v);
}
++c;
}
//cout << c << endl;

if (SZ(cur)) path.PB(cur);
else if (!c) cur.PB(u), path.PB(cur);
}
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

#define a to[i^1]
#define b to[i]

Rush{

RST(hd, deg, vis); CLR(path);

FOR_C(i, 2, RD(n)<<1){
RD(a, b);
suc[i] = hd[a], hd[a] = i++;
suc[i] = hd[a], hd[a] = i;
}

dfs();

OT(SZ(path)); REP(i, SZ(path)){
printf("%d", path[i][0]); FOR(j, 1, SZ(path[i])) printf(" %d", path[i][j]);
puts("");
}
}
}
```

（无论从哪方面看。。这题似乎。。贪心都要更优越一些。。/w\。。