CF1320E Treeland and Viruses

CF1320E Treeland and Viruses

仔细观察题目,Go directly to the virtual tree.

Consider the trick again dp,I found that there are many priorities that are not very easy to do.

考虑 spfa,After a spot is found to be infected,Other viruses can't get past this point,不太好做.

Consider priority queues,The optimal point is updated each time,Clearly correct.

时间复杂度 $\mathcal{O}(n\log n)$.

#include<bits/stdc++.h>

using namespace std;

//#define int long long
typedef long long ll;
#define ha putchar(' ')
#define he putchar('\n')

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

inline void write(int x)
{
    
	if(x < 0)
	{
    
		putchar('-');
		x = -x;
	}
	if(x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

const int _ = 2e5 + 10;

int n, Q, k, m, t, s[_], w[_];

bool vis[_];

int cnt, dfn[_], fa[_], siz[_], hson[_], top[_], dep[_];
 
vector<int> d[_], v, p, q, a, b, g[_];

bool cmp(int u, int v)
{
    
	return dfn[u] < dfn[v];
}

void dfs1(int u, int D = 1)
{
    
	dep[u] = D, siz[u] = 1, dfn[u] = ++cnt;
	for(int v : d[u])
	{
    
		if(siz[v]) continue;
		fa[v] = u;
		dfs1(v, D + 1);
		siz[u] += siz[v];
		if(siz[hson[u]] < siz[v]) hson[u] = v;
	}
}

void dfs2(int u, int tf)
{
    
	top[u] = tf;
	if(hson[u]) dfs2(hson[u], tf);
	for(int v : d[u])
	{
    
		if(top[v]) continue;
		dfs2(v, v);
	}
}

int LCA(int u, int v)
{
    
// cout << "1\n";
	while(top[u] != top[v])
	{
    
// cout << "2\n";
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		u = fa[top[u]];
	}
// cout << "3\n";
	return dep[u] > dep[v] ? v : u;
}

int Dis(int x, int y)
{
    
	return dep[x] + dep[y] - 2 * dep[LCA(x, y)];
}

void build()
{
    
	q = p;
	for(int x : p)
	{
    
		int lca = LCA(x, s[t]);
		if(lca != s[t])
		{
    
			while(t && dep[s[t - 1]] >= dep[lca])
			{
    
				g[s[t]].push_back(s[t - 1]), g[s[t - 1]].push_back(s[t]);
				--t;
			}
			if(s[t] != lca)
			{
    
				g[s[t]].push_back(lca), g[lca].push_back(s[t]);
				s[t] = lca;
				q.push_back(lca);
			}
		}
		s[++t] = x;
	}
	if(t)
		while (--t) g[s[t]].push_back(s[t + 1]), g[s[t + 1]].push_back(s[t]);
	p = q;
}

struct abc
{
    
	int d, i, x, r;
	abc()
	{
    
		
	}
	abc(int d, int i, int x) : d(d), i(i), x(x)
	{
    
// if(!w[x])
// {
    
 cout << x << "\n";
 cout << "!!!!!!!!!\n";
// exit(0);
// }
		r = d ? (d - 1) / w[x] : -1;
	}
	bool operator < (const abc o) const
	{
    
		return r == o.r ? i < o.i : r < o.r;
	}
} dis[_];

struct Node
{
    
	abc a; int id;
	bool operator < (const Node &t) const
	{
    
		return a.r == t.a.r ? a.i > t.a.i : a.r > t.a.r;
	}
};

void dij()
{
    
	priority_queue<Node> q;
	for(int x : p)
	{
    
		dis[x].r = dis[x].i = n;
		vis[x] = 0;
	}
	for(int i = 0; i < a.size(); i++)
	{
    
		dis[a[i]] = abc(0, i + 1, a[i]);
		q.push({
    dis[a[i]], a[i]});
	}
	while(!q.empty()) {
    
		int x = q.top().id;
		q.pop();
		if (vis[x]) continue;
		vis[x] = 1;
// cout <<x << "\n";
		for (int y : g[x])
		{
    
// cout << ": " << y << "\n";
			abc nw = abc(dis[x].d + Dis(x, y), dis[x].i, dis[x].x);
			if (nw < dis[y])
			{
    
				dis[y] = nw;
				q.push({
    dis[y], y});
			}
		}
	}
	for(int x : b) write(dis[x].i), ha;
	he;
}

signed main()
{
    
	n = read();
	for(int i = 1, u, v; i < n; ++i)
	{
    
		u = read(), v = read();
		d[u].push_back(v);
		d[v].push_back(u);
	}
	dfs1(1), dfs2(1, 1);
	Q = read();
	while(Q--)
	{
    
		k = read(), m = read();
		v.clear(), p.clear(), a.clear(), q.clear(), b.clear();
		for(int i = 1, x, y; i <= k; ++i)
		{
    
			x = read(), y = read();
			a.push_back(x);
			v.push_back(x), w[x] = y;
		}
		for(int i = 1, x; i <= m; ++i)
		{
    
			x = read();
			b.push_back(x);
			v.push_back(x);
		}
		sort(v.begin(), v.end(), cmp);
		for(int i = 0; i < v.size() - 1; ++i)
			if(v[i] != v[i + 1]) p.push_back(v[i]);
		p.push_back(v[v.size() - 1]);
		build();
// for(int x : p) cout << x <<" ";
// cout << "!!\n";
		dij();
		for(int x : p) g[x].clear();
	}
}

/* 7 1 2 1 3 2 4 2 5 3 6 3 7 3 2 2 4 1 7 1 1 3 2 2 4 3 7 1 1 3 3 3 1 1 4 100 7 100 1 2 3 */