{"problem":{"name":"[POI 2002] 商务旅行","description":{"content":"某地首都的商人要经常到其他城镇去做生意，他们会按自己的路线去走。 有 $N$ 个城镇，首都编号为 $1$。商人从首都出发，其他各城镇之间都有道路连接。 任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。如果从首都出发，能到达任意一个城镇。 请你求出商人最短的旅行时间。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":100,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8855"},"statements":[{"statement_type":"Markdown","content":"某地首都的商人要经常到其他城镇去做生意，他们会按自己的路线去走。\n\n有 $N$ 个城镇，首都编号为 $1$。商人从首都出发，其他各城镇之间都有道路连接。\n\n任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。如果从首都出发，能到达任意一个城镇。\n\n请你求出商人最短的旅行时间。\n\n## Input\n\n第一行有一个整数 $N$，为城镇的数目。\n\n接下来 $N-1$ 行，每行两个整数 $a$ 和 $b$，表示城镇 $a$ 和城镇 $b$ 有公路连接。\n\n接下来一个整数 $M$，然后 $M$ 行，每行有该商人需要顺次经过的各城镇编号。\n\n## Output\n\n一行，输出商人最短的旅行时间。\n\n[samples]\n\n## Note\n\n数据范围：$1 \\le N \\le 30000$。**保证公路网络不会存在环。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8855","tags":["2002","POI（波兰）","最近公共祖先 LCA"],"sample_group":[["5\n1 2\n1 5\n3 5\n4 5\n4\n1\n3\n2\n5","7"]],"created_at":"2026-03-03 11:09:25"}}