我爱珂朵莉

我永远喜欢珂朵莉

http://www.nowcoder.com/questionTerminal/1c98a614b62c489e8365eaacd536a3c6

include<bits/stdc++.h>

define lson (o<<1)

define rson (o<<1|1)

define fi first

define sc second

define dbg(x) cout<<#x<<" = "<<(x)<<endl;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
using namespace std;
const double pi=acos(-1);
const double eps=1e-6;
inline int lowbit(int x){return x&(-x);}
inline int read(){
int f=1,x=0;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
return fx;
}
template<typename t=""> inline T max(T x,T y,T z){return max(max(x,y),z);}
template<typename t=""> inline T min(T x,T y,T z){return min(min(x,y),z);}
template<typename t=""> inline T sqr(T x){return x</typename></typename></typename>
x;}
template<typename t=""> inline void checkmax(T &x,T y){x=max(x,y);}
template<typename t=""> inline void checkmin(T &x,T y){x=min(x,y);}
template<typename t=""> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x</typename></typename></typename>
=f;
}
template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){
A ans=1;
for(;p;p>>=1,x=1LLxx%yql)if(p&1)ans=1LLxans%yql;
return ans;
}
struct FastIO{
static const int S=1310720;
int wpos;char wbuf[S];
FastIO():wpos(0) {}
inline int xchar(){
static char buf[S];
static int len=0,pos=0;
if(pos==len)pos=0,len=fread(buf,1,S,stdin);
if(pos==len)return -1;
return buf[pos++];
}
inline int read(){
int c=xchar(),x=0;
while(c<=32&&~c)c=xchar();
if(c==-1)return -1;
for(;'0'<=c&&c<='9';c=xchar())x=x*10+c-'0';
return x;
}
}io;
//#define read io.read
const int maxn=10000010;
struct poi{int too,pre;}e[maxn<<1];
int n,m,x,y,z,tot,cnt,ans,a,b,t,cntt;
int last[maxn],size[maxn],fa[maxn],dep[maxn],son[maxn],w[maxn],top[maxn],mx[maxn],q[maxn],s[maxn];

inline void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}
void dfs1(int x){
size[x]=1;
for(int i=last[x];i;i=e[i].pre){
int too=e[i].too;
if(too==fa[x])continue;
fa[too]=x;
dep[too]=dep[x]+1;
dfs1(too);
if(size[too]>size[son[x]])son[x]=too;
size[x]+=size[too];
}
}
void dfs2(int x,int tp){
mx[x]=w[x]=++cnt;top[x]=tp;
if(son[x])dfs2(son[x],tp),mx[x]=max(mx[x],mx[son[x]]);
for(int i=last[x];i;i=e[i].pre)
if(e[i].too!=son[x]&&e[i].too!=fa[x])
dfs2(e[i].too,e[i].too),mx[x]=max(mx[x],mx[e[i].too]);
}
inline void work(int x,int y){
int f1=top[x],f2=top[y];
while(f1!=f2){
if(dep[f1]<dep[f2])swap(x,y),swap(f1,f2);
// printf("QWQ%d %d\n",w[f1],w[x]);
q[++cntt]=w[f1];s[w[f1]]++;
q[++cntt]=w[x]+1;s[w[x]+1]--;
x=fa[f1];f1=top[x];
}
if(dep[x]<dep[y])swap(x,y);
q[++cntt]=w[y];s[w[y]]++;
q[++cntt]=w[x]+1;s[w[x]+1]--;
// printf("QWQ%d %d\n",w[y],w[x]);
}
int main(){
read(n);read(m);
for(int i=1;i<n;i++)read(x),read(y),add(x,y),add(y,x);
dfs1(1);dfs2(1,1);
for(int i=1;i<=m;i++){
read(a);read(b);read(t);cntt=0;
for(int i=1;i<=a;i++)read(x),read(y),work(x,y);
for(int i=1;i<=b;i++){
read(x);//printf("QWQ%d %d\n",w[x],mx[x]+1);
q[++cntt]=w[x];s[w[x]]++;
q[++cntt]=mx[x]+1;s[mx[x]+1]--;
}
q[++cntt]=n+1;q[++cntt]=1;sort(q+1,q+1+cntt);
cntt=unique(q+1,q+1+cntt)-q-1;
int sum=0,now=1,ans=0;
for(int i=1;i<cntt;i++){
sum+=s[q[i]];
if(sum>=t)ans+=q[i+1]-q[i];
}
for(int i=1;i<=cntt;i++)s[q[i]]=0;
printf("%d\n",ans);
}
return 0;
}

全部评论

相关推荐

粗心的雪碧不放弃:纯学历问题,我这几个月也是一直优化自己的简历,后来发现优化到我自己都觉得牛逼的时候,发现面试数量也没有提升,真就纯学历问题
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务