트리 압축

#include<bits/stdc++.h>
using namespace std;

#define INF 4000000000000000000
#define ll long long

int N, Q;
vector<pair<int, int> > g[500001]; // 인접 리스트
int st[500001]; // 정점의 DFS preorder 순서
int h[500001]; // 정점의 level
ll D[500001]; // 정점에서 루트까지 가는 경로의 길이
int p[19][500001]; // 스파스 테이블

int type[500001]; // 현재 쿼리에서 정점이 어떤 집합에 속하는가?
vector<pair<int, ll> > G[500001]; // 압축된 트리
ll S[500001], T[500001]; // DP
ll res;

void DFS(int n, int prev)
{
	static int ord = 0;
	st[n] = ++ord;
	h[n] = h[prev] + 1;
	p[0][n] = prev;
	for(auto [next,cost] : g[n])
	{
		if (next == prev) continue;
		D[next] = D[n] + cost;
		DFS(next, n);
	}
}

int LCA(int a, int b)
{
	if (h[a] < h[b]) swap(a, b);
	int gap = h[a]-h[b];
	for(int i=0; i<19; i++)
		if (gap & 1<<i)
			a = p[i][a];
	if (a == b) return a;
	for(int i=18; i>=0; i--)
		if (p[i][a] != p[i][b])
			a = p[i][a], b = p[i][b];
	return p[0][a];
}

void DFS2(int n)
{
	S[n] = T[n] = INF;
	if (type[n] == 1) S[n] = 0;
	else if (type[n] == 2) T[n] = 0;
	for(auto [next,cost] : G[n])
	{
		DFS2(next);
		S[n] = min(S[n], S[next] + cost);
		T[n] = min(T[n], T[next] + cost);
	}
	// 현재 시점에서
	// S[n] : n의 서브트리에서 n과 가장 가까운 type=1 정점과의 거리
	// T[n] : n의 서브트리에서 n과 가장 가까운 type=2 정점과의 거리
	// 가 된다.
}

void DFS3(int n, ll s, ll t)
{
	// 현재 시점에서
	// s : n의 부모 정점 p와 가장 가까운 type=1 정점과의 거리 + cost(n, p)
	// t : n의 부모 정점 p와 가장 가까운 type=2 정점과의 거리 + cost(n, p)
	// 가 된다.
	s = min(s, S[n]);
	t = min(t, T[n]);
	// 현재 시점에서
	// s : n과 가장 가까운 type=1 정점과의 거리
	// t : n과 가장 가까운 type=2 정점과의 거리
	// 가 된다.
	res = min(res, s + t);
	for(auto [next, cost] : G[n])
		DFS3(next, s + cost, t + cost);
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> Q;
	for(int i=0; i<N-1; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		a++; b++; // 1-based
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}
	// Euler Tour와 LCA 전처리
	DFS(1, 0);
	for(int i=1; i<19; i++)
		for(int j=1; j<=N; j++)
			p[i][j] = p[i-1][p[i-1][j]];

	while(Q--)
	{
		vector<int> A;
		int s, t, x, y;
		cin >> s >> t;
		while(s--)
		{
			cin >> x;
			x++; // 1-based
			A.push_back(x);
			type[x] = 1;
		}
		while(t--)
		{
			cin >> y;
			y++; // 1-based
			A.push_back(y);
			type[y] = 2;
		}

		// 1. Euler Tour 순으로 정렬하기
		sort(A.begin(), A.end(), [&](int a, int b){ return st[a] < st[b]; });

		// 2. 인접한 정점 쌍들의 LCA를 추가하기
		int sz = A.size();
		for(int i=1; i<sz; i++)
			A.push_back(LCA(A[i-1], A[i]));
		sort(A.begin(), A.end(), [&](int a, int b){ return st[a] < st[b]; });
		A.erase(unique(A.begin(), A.end()), A.end());

		// 3. 압축된 트리를 명시적으로 구성하기
		for(int i=1; i<A.size(); i++)
		{
			int prev = LCA(A[i-1], A[i]), n = A[i];
			G[prev].push_back({n, D[n]-D[prev]});
		}

		// 4. 새로운 트리에서 정답 구하기
		res = INF;
		DFS2(A[0]);
		DFS3(A[0], INF, INF);
		cout << res << "\n";

		// 다음 쿼리를 위한 초기화
		for(int n : A)
		{
			type[n] = 0;
			G[n].clear();
		}
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

int N, M;
vector<int> g[100001];
bool vis[100001];
int st[100001], h[100001], p[17][100001];
vector<pair<int, int> > backedge;
vector<int> A;

int pp[100001]; // 압축된 트리의 부모
map<pair<int, int>, int> ord; // 간선 -> 번호
pair<int, int> edg[78]; // 번호 -> 간선
bitset<78> cycle[16]; // 기초 사이클들의 XOR로 만들어진 간선 리스트
vector<int> G[100001]; // 기초 사이클들의 XOR로 만들어진 그래프

void DFS(int n, int prev)
{
	static int ord = 0;
	vis[n] = true;
	st[n] = ++ord;
	h[n] = h[prev] + 1;
	p[0][n] = prev;
	for(int next : g[n])
	{
		if (next == prev) continue;
		if (vis[next])
		{
			if (h[n] > h[next]) // 역방향 간선 발견
			{
				backedge.push_back({n, next});
				A.push_back(n);
				A.push_back(next);
			}
			continue;
		}
		DFS(next, n);
	}
}

int LCA(int a, int b)
{
	if (h[a] < h[b]) swap(a, b);
	int gap = h[a]-h[b];
	for(int i=0; i<17; i++)
		if (gap & 1<<i)
			a = p[i][a];
	if (a == b) return a;
	for(int i=16; i>=0; i--)
		if (p[i][a] != p[i][b])
			a = p[i][a], b = p[i][b];
	return p[0][a];
}

void DFS2(int n) // 컴포넌트 방문 체크
{
	vis[n] = true;
	for(int next : G[n])
	{
		if (vis[next]) continue;
		DFS2(next);
	}
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M;
	for(int i=0; i<M; i++)
	{
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	// Euler Tour와 LCA 전처리, backedge들 구하기
	DFS(1, 0);
	for(int i=1; i<17; i++)
		for(int j=1; j<=N; j++)
			p[i][j] = p[i-1][p[i-1][j]];

	// 트리 압축
	// 1. Euler Tour 순으로 정렬하기
	sort(A.begin(), A.end(), [&](int a, int b){ return st[a] < st[b]; });
	A.erase(unique(A.begin(), A.end()), A.end());

	// 2. 인접한 정점 쌍들의 LCA를 추가하기
	int sz = A.size();
	for(int i=1; i<sz; i++)
		A.push_back(LCA(A[i-1], A[i]));
	sort(A.begin(), A.end(), [&](int a, int b){ return st[a] < st[b]; });
	A.erase(unique(A.begin(), A.end()), A.end());

	// 3. 압축된 트리의 부모 배열 만들기
	for(int i=1; i<A.size(); i++)
	{
		int prev = LCA(A[i-1], A[i]), n = A[i];
		pp[n] = prev;
	}

	// 4. 새로운 트리에서 정답 구하기
	int E = 0; // 간선의 개수
	for(int i=0; i<backedge.size(); i++) // 기초 사이클들 구하기
	{
		auto [a,b] = backedge[i];
		auto insert = [&](int x, int y) // 간선 번호 매기기
		{
			if (ord.find({x, y}) == ord.end())
			{
				ord[{x, y}] = E;
				edg[E] = {x, y};
				E++;
			}
			cycle[i][ord[{x, y}]] = true;
		};

		insert(a, b);
		while(a != b) // backedge를 타고 올라가기
		{
			insert(pp[a], a);
			a = pp[a];
		}
	}

	// 최대 2^16가지 사이클 후보들을 완전 탐색
	memset(vis, 0, sizeof(vis));
	int res = 0;
	for(int i=1; i<(1<<backedge.size()); i++)
	{
		bitset<78> bs;
		for(int j=0; j<backedge.size(); j++)
			if (i & 1<<j)
				bs ^= cycle[j];

		// 기초 사이클들의 XOR로 만들어진 그래프 구성하기
		vector<int> v;
		for(int j=0; j<78; j++)
			if (bs[j])
			{
				auto [a,b] = edg[j];
				v.push_back(a);
				v.push_back(b);
				G[a].push_back(b);
				G[b].push_back(a);
			}
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());

		// simple cycle인가?
		// = 모든 정점의 degree가 0 또는 2이면서 컴포넌트가 하나인가?
		DFS2(v[0]);
		int die = 0;
		for(int n : v)
			if (G[n].size() != 2 || vis[n] == false)
				die = 1;
		if (!die) res++;

		// 초기화
		for(int n : v)
		{
			vis[n] = false;
			G[n].clear();
		}
	}
	cout << res << "\n";
	return 0;
}