Jzoj P 5914盟主の憂慮_思考+そして調査集

テーマ:
N N N個のノードを有する木のN−1 N−1 N−1辺を与え,これらの辺を通過するのに費用を消費する必要はなく,M M本の密道を与え,w i w_i wi経由で,最初のN−1 N−1 N−1辺をそれぞれ切断し,2点を切断するたびに残りの辺と密道を通ってこの2点を連通させるのにかかる最小限の費用を求め,連通できないのが−1である.
N , M < = 100 , 000 N,M<=100,000 N,M<=100,000
分析:
木の縁を1本取り除いた後、通る密道はせいぜい1本で、1本の密道(u,v,w)に対して、uからvへの経路上の辺の答えはせいぜいwで、暴力的に更新すればよいことがわかりやすい.すべての密道を重み値に従って小さいものから大きいものに並べ替えます.1本の密道(u,v,w)について、uからvへの経路上のエッジにエッジが存在する前に上書きされていない場合、このエッジを説明する答えはwである.各集合の深さが最小のノードを維持し、密道(u,v,w)については、uがその集合の中で深さが最小の点を見つけるたびに、この点と父の連辺は必ず上述のエッジであり、このエッジの答えをwに更新し、uが存在する集合の深さが最も小さいノードがuとvのlcaより小さいまで、このノードを父親と統合し、vに対して同じプロセスを行えばよい.
コード:

#include 
#include 
#include 
#include 
#include 
#include 
#define N 100005

using namespace std;

struct Node { int rank, To, nxt; }e[N*2];
struct Code { int u, v, w; }a[N];
int Answer[N], belong[N], Oank[N], deep[N], fa[N], ls[N], n, m, cnt;

int read(int &x)
{
    int f = 1; x = 0; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
	while (s >= '0' && s <= '9') { x = x * 10 + (s - '0'); s = getchar(); }
	x = x * f;	
}

void Addedge(int u, int v, int rank)
{
    e[++cnt].To = v, e[cnt].nxt = ls[u], e[cnt].rank = rank, ls[u] = cnt;
	e[++cnt].To = u, e[cnt].nxt = ls[v], e[cnt].rank = rank, ls[v] = cnt;	
}

void dfs(int x, int father)
{
	fa[x] = father;
    for (int i = ls[x]; i; i = e[i].nxt)
	{
		if (e[i].To == father) continue;
	    int y = e[i].To; deep[y] = deep[x] + 1;
		dfs(y, x);	Oank[y] = e[i].rank;
	}	
}

int Find(int x)
{
	if (belong[x] == x) return x;
	return (belong[x] = Find(belong[x]));
}

bool cmp(Code aa, Code bb)
{
	return aa.w < bb.w;
}

int main()
{
	freopen("worry.in", "r", stdin);
	freopen("worry.out", "w", stdout);
	read(n); read(m);
	for (int i = 1; i < n; i++)
	{
		int u, v; read(u); read(v); Addedge(u, v, i);
	}
	for (int i = 1; i <= n; i++) belong[i] = i;
	deep[1] = 1, dfs(1, 0);
	for (int i = 1; i <= m; i++)
		read(a[i].u), read(a[i].v), read(a[i].w);
	sort(a + 1, a + m + 1, cmp);
	for (int i = 1; i <= m; i++)
	{
        int xx = Find(a[i].u), yy = Find(a[i].v);
        while (xx != yy)
        {	
           if (deep[xx] < deep[yy]) swap(xx, yy);
		   Answer[Oank[xx]] = a[i].w, belong[xx] = Find(fa[xx]), xx = belong[xx];
       }
	}																																																																																																																																																																														
	for (int i = 1; i < n; i++) 
	     if (!Answer[i]) printf("-1
"); else printf("%d
", Answer[i]);
}