# 某島

… : "…アッカリ～ン . .. . " .. .
October 4, 2014

## PKU Campus 2011

Problem B. A Problem about Tree

```const int N = int(1e4) + 9, M = int(1e4) + 9;
int fa[N]; VI todo[N], adj[N]; int path[N];
int n, m;

int vis[N];

struct qry{
int u, r, z;
void in(){
z = -1;
scanf("%d %d", &u, &r);
}
void out(){
if (z == -1) z = fa[r];
printf("%d\n", z);
}
} Q[M];

void dfs(int u = 1){

vis[u] = 1;

ECH(it, todo[u]){
int id = *it, r = Q[id].r;
Q[id].z = vis[r] == 1 ? path[r] : -1;
}

int v = *it; if (v != fa[u]){
fa[v] = u;
path[u] = v;
dfs(v);
}
}

vis[u] = 0;
}

int main(){

//freopen("e.txt", "r", stdin);

int T; cin >> T; while (T--){

cin >> n >> m;

DO(n-1){
int a, b; scanf("%d %d", &a, &b);
}

REP(i, m){
Q[i].in();
todo[Q[i].u].PB(i);
}

dfs();
REP(i, m) Q[i].out();
}
}

```

Dijkstra + Dp

```const int N = int(5e2) + 9;

int d[N][N];
int n, m;

priority_queue<PII, vector<PII>, greater<PII> > Q;

void Dijkstra(int d[], int s){

fill(d, d+n, INF); d[s] = 0; Q.push(MP(0, s));

while (!Q.empty()){
int u = Q.top().se, du = Q.top().fi; Q.pop(); if (du != d[u]) continue;

int v = it->fi, w = it->se;
if (d[v] > d[u] + w){
d[v] = d[u] + w;
Q.push(MP(d[v], v));
}
}
}
}

int dp[2][N][N];

int main(){

//freopen("in.txt", "r", stdin);

while (~scanf("%d %d", &n, &m)){

REP(i, m){
int a, b, c; scanf("%d %d %d", &a, &b, &c);
if (a == b) continue;
}

REP(i, n) Dijkstra(d[i], i);
int p = 0, q = 1; swap(p, q); FLC(dp[p], 0x3f); dp[p][0][0] = 0;

FOR(i, 1, n){
swap(p, q); int a = i-1; FLC(dp[p], 0x3f);
#define u dp[q][b]
REP(b, n) REP(c, n) if (u != INF){
checkMin(dp[p][b], u + d[a][i]);
checkMin(dp[p][a], u + d[b][i]);
checkMin(dp[p][a][b], u + d[i]);
}
}

int z = INF; REP(i, n) REP(j, n) if (dp[p][i][j] != INF){
checkMin(z, dp[p][i][j] + d[n-1][0] + d[i][0] + d[j][0]);
}
cout << z << endl;
}
}

```