Codeforces 587C Duff in the Army 题解

Codeforces 587C Duff in the Army 题解

题意

给定一棵有$n$个结点的树，某些结点上有一些数，总共有$m$个数，有$q (1\le n,m,k\le 10^5)$次询问。

每次询问给定$u,v,a (1\le u,v\le n,1\le a\le10)$，求出 在$u$到$v$的路径上所有的结点上的数中，前$a$小的数(如果总数小于$a$，则输出所有的数)。

题解

在树中，从$u$到$v$的路径上，$a\le10$，从这三个条件可以想到用树链剖分，线段树中每个结点维护的是一个长度小于等于$10$的vector，表示的是这些点中前$10$小的数，可以$O(1)$合并。

因为没有修改，所以省去了很多。程序也不是太难写。

时间复杂度$O(q\log n)$。

Tip: 可以用LCA，也是维护前$10$小的数，时间复杂度同样。

程序

// #pragma GCC optimize(2)
// #pragma G++ optimize(2)
// #pragma comment(linker,"/STACK:102400000,102400000")

// #include <bits/stdc++.h>
#include <map>
#include <set>
#include <list>
#include <array>
#include <cfenv>
#include <cmath>
#include <ctime>
#include <deque>
#include <mutex>
#include <queue>
#include <ratio>
#include <regex>
#include <stack>
#include <tuple>
#include <atomic>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <chrono>
#include <cstdio>
#include <cwchar>
#include <future>
#include <limits>
#include <locale>
#include <memory>
#include <random>
#include <string>
#include <thread>
#include <vector>
#include <cassert>
#include <climits>
#include <clocale>
#include <complex>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <ctgmath>
#include <cwctype>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <sstream>
#include <ccomplex>
#include <cstdbool>
#include <iostream>
#include <typeinfo>
#include <valarray>
#include <algorithm>
#include <cinttypes>
#include <cstdalign>
#include <stdexcept>
#include <typeindex>
#include <functional>
#include <forward_list>
#include <system_error>
#include <unordered_map>
#include <unordered_set>
#include <scoped_allocator>
#include <condition_variable>
// #include <conio.h>
// #include <windows.h>
using namespace std;

typedef long long LL;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef float fl;
typedef double ld;
typedef long double LD;
typedef pair<int,int> pii;
#if (WIN32) || (WIN64) || (__WIN32) || (__WIN64) || (_WIN32) || (_WIN64) || (WINDOWS)
#define lld "%I64d"
#define llu "%I64u"
#else
#define lld "%lld"
#define llu "%llu"
#endif
#define ui(n) ((unsigned int)(n))
#define LL(n) ((long long)(n))
#define ull(n) ((unsigned long long)(n))
#define fl(n) ((float)(n))
#define ld(n) ((double)(n))
#define LD(n) ((long double)(n))
#define char(n) ((char)(n))
#define Bool(n) ((bool)(n))
#define fixpoint(n) fixed<<setprecision(n)

const int INF=1061109567;
const int NINF=-1044266559;
const LL LINF=4557430888798830399;
const ld eps=1e-15;
#define MOD (1000000007)
#define PI (3.1415926535897932384626433832795028841971)

/*
#define MB_LEN_MAX 5
#define SHRT_MIN (-32768)
#define SHRT_MAX 32767
#define USHRT_MAX 0xffffU
#define INT_MIN (-2147483647 - 1)
#define INT_MAX 2147483647
#define UINT_MAX 0xffffffffU
#define LONG_MIN (-2147483647L - 1)
#define LONG_MAX 2147483647L
#define ULONG_MAX 0xffffffffUL
#define LLONG_MAX 9223372036854775807ll
#define LLONG_MIN (-9223372036854775807ll - 1)
#define ULLONG_MAX 0xffffffffffffffffull
*/

#define MP make_pair
#define MT make_tuple
#define All(a) (a).begin(),(a).end()
#define pall(a) (a).rbegin(),(a).rend()
#define Log(x,y) log(x)/log(y)
#define SZ(a) ((int)(a).size())
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define rep1(i,n) for(int i=1;i<=((int)(n));i++)
#define repa(i,a,n) for(int i=((int)(a));i<((int)(n));i++)
#define repa1(i,a,n) for(int i=((int)(a));i<=((int)(n));i++)
#define repd(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define repd1(i,n) for(int i=((int)(n));i>=1;i--)
#define repda(i,n,a) for(int i=((int)(n));i>((int)(a));i--)
#define repda1(i,n,a) for(int i=((int)(n));i>=((int)(a));i--)
#define FOR(i,a,n,step) for(int i=((int)(a));i<((int)(n));i+=((int)(step)))
#define repv(itr,v) for(__typeof((v).begin()) itr=(v).begin();itr!=(v).end();itr++)
#define repV(i,v) for(auto i:v)
#define repE(i,v) for(auto &i:v)
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x) MS(x,0)
#define MINF(x) MS(x,63)
#define MCP(x,y) memcpy(x,y,sizeof(y))
#define sqr(x) ((x)*(x))
#define UN(v) sort(All(v)),v.erase(unique(All(v)),v.end())
#define filein(x) freopen(x,"r",stdin)
#define fileout(x) freopen(x,"w",stdout)
#define fileio(x)\
	freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout)
#define filein2(filename,name) ifstream name(filename,ios::in)
#define fileout2(filename,name) ofstream name(filename,ios::out)
#define file(filename,name) fstream name(filename,ios::in|ios::out)
#define Pause system("pause")
#define Cls system("cls")
#define fs first
#define sc second
#define PC(x) putchar(x)
#define GC(x) x=getchar()
#define Endl PC('\n')
#define SF scanf
#define PF printf

#define j0 J0
#define j1 J1
#define jn Jn
#define y0 Y0
#define y1 Y1
#define yn Yn

inline int Read()
{
    int X=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
	return w?-X:X;
}
inline void Write(int x){if(x<0)putchar('-'),x=-x;if(x>9)Write(x/10);putchar(x%10+'0');}

inline LL powmod(LL a,LL b){LL RES=1;a%=MOD;assert(b>=0);for(;b;b>>=1){if(b&1)RES=RES*a%MOD;a=a*a%MOD;}return RES%MOD;}
inline LL gcdll(LL a,LL b){return b?gcdll(b,a%b):a;}
const int dx[]={0,1,0,-1,1,-1,-1,1};
const int dy[]={1,0,-1,0,-1,-1,1,1};
/************************************************************BEGIN************************************************************/
const int maxn=100010;

struct node
{
	int l,r;
	vector<int> w;
} tree[maxn*4];

int n,m,q,son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn];
vector<int> e[maxn],w[maxn],wt[maxn],ans;

inline void update(vector<int> &a,vector<int> b)
{
	int l=0,r=0;
	vector<int> c;

	while(c.size()<10&&(l!=a.size()||r!=b.size()))
	{
		if(l==a.size()) c.push_back(b[r++]); else if(r==b.size()) c.push_back(a[l++]);
		else
		{
			if(a[l]<b[r]) c.push_back(a[l++]); else c.push_back(b[r++]);
		}
	}

	a=c;
}

inline void seg_build(int l,int r,int k)
{
	tree[k].l=l;tree[k].r=r;
	
	if(l==r)
	{
		tree[k].w=wt[l];
		return;
	}
	
	int mid=(l+r)/2;
	seg_build(l,mid,k*2);
	seg_build(mid+1,r,k*2+1);
	
	update(tree[k].w,tree[k*2].w);
	update(tree[k].w,tree[k*2+1].w);
}

inline void seg_range_sum(int l,int r,int k) 
{
	if(tree[k].l>=l&&tree[k].r<=r) return update(ans,tree[k].w);

	int mid=(tree[k].l+tree[k].r)/2;
	if(l<=mid) seg_range_sum(l,r,k*2);
	if(r>mid) seg_range_sum(l,r,k*2+1);
}

inline void dfs1(int x,int f,int deep)
{
	dep[x]=deep;
	fa[x]=f;
	siz[x]=1;
	
	for(int i=0;i<e[x].size();i++)
	{
		int y=e[x][i];
		if(y!=f)
		{
			dfs1(y,x,deep+1);
			siz[x]+=siz[y];
			
			if(son[x]==0||siz[y]>siz[son[x]]) son[x]=y;
		}
	}
}

inline void dfs2(int x,int tp)
{
	id[x]=++cnt;
	wt[cnt]=w[x];
	top[x]=tp;
	
	if(!son[x]) return;
	dfs2(son[x],tp);
	
	for(int i=0;i<e[x].size();i++)
	{
		int y=e[x][i];
		if(y!=fa[x]&&y!=son[x]) dfs2(y,y);
	}
}

inline void hld_sum(int x,int y,int a)
{
	ans.clear();
	
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		seg_range_sum(id[top[x]],id[x],1);
		x=fa[top[x]];
	}
	
	if(dep[x]>dep[y]) swap(x,y);
	
	seg_range_sum(id[x],id[y],1);

	PF("%d ",min(SZ(ans),a));
	rep(i,min(SZ(ans),a)) PF("%d ",ans[i]);
	PF("\n");
}

int main()
{
	SF("%d%d%d",&n,&m,&q);
	for(int i=1;i<n;i++)
	{
		int x,y;SF("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	rep1(i,m)
	{
		int x;SF("%d",&x);
		if(w[x].size()<10) w[x].push_back(i);
	}
	
	dfs1(1,0,1);
	dfs2(1,1);
	seg_build(1,n,1);
	
	while(q--)
	{
		int u,v,a;SF("%d%d%d",&u,&v,&a);
		hld_sum(u,v,a);
	}
	
	return 0;
}
/*************************************************************END**************************************************************/