HDU多校2
赛中五题，总结：签到、签到、枚举、枚举以及一道讨论到头大的线段树
1002
题意：去掉字符串中的“std::make_tuple”。
思路：遇到's'直接i+=14即可。遍历输出。
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll b[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],a[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;
bool cmp(qq u,qq v){
return u.x>v.x;
}
bool cmp1(qq u,qq v){
return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
return u>v;
}};//shun序
pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;
void solve(){
scanf("%s",s+1);
n=strlen(s+1);m=0;
L(i,1,n){
if(s[i]=='s')i+=14;
else a[++m]=s[i];
}
L(i,1,m)printf("%c",a[i]);printf("\n");
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll t=1;
scanf("%lld",&t);
while(t--)solve();
}
1012
题意：三种硬币价值分别为7、31、365，求凑出n元需要的硬币最小数量，或者不能凑出n。
思路：因为是数量最小，所以很明显的，7的数量不能超过31个，31的数量不能超过365个。直接枚举7的数量和31的数量，求解365的数量，然后求数量和最小值即可，复杂度O(31*365*t)，约为1e7。（当然可以用贪心，但是有点小复杂）
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll b[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],a[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;
bool cmp(qq u,qq v){
return u.x>v.x;
}
bool cmp1(qq u,qq v){
return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
return u>v;
}};//shun序
pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;
void solve(){
scanf("%lld",&n);
ans=inf;
L(i,0,30)L(j,0,364){
m=n-i*7-j*31;
if(m%365==0&&m>=0)ans=min(ans,i+j+m/365);
}
if(ans==inf)printf("-1\n");
else printf("%lld\n",ans);
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll t=1;
scanf("%lld",&t);
while(t--)solve();
}
1009
题意：数学题，已知：
已知 P,Q,e，求 r。
思路：，且M是质数。因此枚举 (P*Q-1) 的质因数表示M，然后通过式3计算r，并通过式2验算即可。
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=2e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;
bool cmp(qq u,qq v){
return u.x>v.x;
}
bool cmp1(qq u,qq v){
return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
return u>v;
}};//shun序
pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;
bool visprime[N];
ll prime[N];
void oulasai(ll n){
cnt=0;
L(i,2,n){
if(!visprime[i])prime[++cnt]=i;
L(j,1,cnt){
if(i*prime[j]>n) break;
visprime[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
}
void solve(){
ll e,r,p,q,m;
scanf("%lld%lld%lld",&p,&q,&e);
n=0;
k=p*q-1;mx=max(e,max(p,q));
L(i,1,cnt){
if(prime[i]*prime[i]>k)break;
if(k%prime[i]==0){
if(prime[i]>mx)a[++n]=prime[i];
while(k%prime[i]==0)k/=prime[i];
}
}
if(k>1)a[++n]=k;
L(i,1,n){
m=a[i];
r=e*q%m;
if(r*p%m==e){
printf("%lld\n",r);
return;
}
}
printf("shuanQ\n");
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
oulasai(2000000);
ll t=1;
scanf("%lld",&t);
while(t--)solve();
}
1007
题意：阅读理解题。给定n个区间，问区间重叠前有几个区间。
（题面太长让队友去开了） 思路：按区间左端点排序，直到有一个区间和后一个区间重叠为止，看前面的区间数量。
1011
题意：给定长为n的数组a，m次询问。每次询问一个区间，求从区间内任选四个数后，分成两对，求两对的平方差（左减右）之和的最大值。
思路： ，因此我们先将所有ai平方。那么问题就转换为了从区间内从左往右选四个数 a,b,c,d，求 max( a-b+c-d , a+b-c-d )。建立线段树，分类讨论左区间与右区间合并时，各状态的最大值即可，具体转译过程可以看代码。
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=16,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r;vector<ll>w;}trs[N*4];
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;
bool cmp(qq u,qq v){
return u.x>v.x;
}
bool cmp1(qq u,qq v){
return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
return u>v;
}};//shun序
pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;
/*
1:-
2:+
3:--
4:-+
5:+-
6:++
7:--+
8:-+-
9:+--
10:-++
11:+-+
12:++-
13:++--
14:+-+-
*/
vector<ll>co(vector<ll>x,vector<ll>y){
vector<ll>res(16);
res[1]=max(x[1],y[1]);
res[2]=max(x[2],y[2]);
res[3]=max(x[3],max(x[1]+y[1],y[3]));
res[4]=max(x[4],max(x[1]+y[2],y[4]));
res[5]=max(x[5],max(x[2]+y[1],y[5]));
res[6]=max(x[6],max(x[2]+y[2],y[6]));
res[7]=max(x[7],max(x[3]+y[2],max(x[1]+y[4],y[7])));
res[8]=max(x[8],max(x[4]+y[1],max(x[1]+y[5],y[8])));
res[9]=max(x[9],max(x[5]+y[1],max(x[2]+y[3],y[9])));
res[10]=max(x[10],max(x[4]+y[2],max(x[1]+y[6],y[10])));
res[11]=max(x[11],max(x[5]+y[2],max(x[2]+y[4],y[11])));
res[12]=max(x[12],max(x[6]+y[1],max(x[2]+y[5],y[12])));
res[13]=max(x[13],max(x[12]+y[1],max(x[6]+y[3],max(x[2]+y[9],y[13]))));
res[14]=max(x[14],max(x[11]+y[1],max(x[5]+y[5],max(x[2]+y[8],y[14]))));
return res;
}
void push_up(ll k){
ll l=k*2,r=k*2+1;
trs[k].w=co(trs[l].w,trs[r].w);
}
void bd_tree(ll k,ll l,ll r){
trs[k].l=l,trs[k].r=r;
if(l==r){
trs[k].w.clear();
trs[k].w.pb(-inf);
trs[k].w.pb(-a[l]);
trs[k].w.pb(a[l]);
L(i,3,14)trs[k].w.pb(-inf);
return;
}
ll mid=(l+r)/2;
bd_tree(k*2,l,mid);
bd_tree(k*2+1,mid+1,r);
push_up(k);
}
vector<ll> query(ll k,ll pl,ll pr){
if(trs[k].l>=pl&&trs[k].r<=pr){
return trs[k].w;
}
ll mid=(trs[k].l+trs[k].r)/2;
if(mid>=pl&&mid+1<=pr){
return co(query(k*2,pl,pr),query(k*2+1,pl,pr));
}
else if(mid>=pl)return query(k*2,pl,pr);
else return query(k*2+1,pl,pr);
}
void solve(){
scanf("%lld%lld",&n,&m);
L(i,1,n){
scanf("%lld",&a[i]);
a[i]*=a[i];
}
bd_tree(1,1,n);
while(m--){
scanf("%lld%lld",&l,&r);
vector<ll>res=query(1,l,r);
ans=max(res[13],res[14]);
printf("%lld\n",ans);
}
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll t=1;
scanf("%lld",&t);
while(t--)solve();
}
1003
题意：给定长为n的数组a，q次操作，有两种操作：
- 选择一个区间，然后复制该区间插入到该区间尾部；
- 询问从左往右数第x个数的值。
（题目特别标注操作1的总次数不会超过20000，让我不禁去往bitset上去想，直到最后二十分钟才想通从后往前做的真谛，结果来不及） 思路：因为不论该数组如何复制变长，询问的x依旧不超过原数组长n。因此我们可以将询问都记录下来，从后往前遍历，举个栗子：当前操作1的区间为 [l,r]，那么在此操作1后面的询问第x个数，如果x>r，那么它就相当于询问此操作1之前的第x-(r-l+1)；如果x<=r，那么该询问就不受此操作1的影响。由于最后输出的是所有询问的异或和，那么一个数被多次询问的话，我们只需将询问次数 mod 2 即可。 考虑bitset，令bi[i]表示当前第i个数是否被询问，对于每个操作1，将区间[r+1,n]右移(r-l+1)位，与区间[1,r]异或即可。
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e5+10,M=16,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll k,x,y;}q[N];
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;
bool cmp(qq u,qq v){
return u.x>v.x;
}
bool cmp1(qq u,qq v){
return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
return u>v;
}};//shun序
pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
bitset<N>bi,ba,bb,bs;
void solve(){
scanf("%lld%lld",&n,&m);
L(i,1,n)scanf("%lld",&a[i]);
bi.reset();ans=0;
L(i,1,m){
scanf("%lld",&k);
if(k==1){
scanf("%lld%lld",&x,&y);
q[i]={k,x,y};
}
else{
scanf("%lld",&x);
q[i]={k,x};
}
}
R(i,m,1){
if(q[i].k==1){
l=q[i].x,r=q[i].y;
ba=bi&(bs>>(N-r-1));
bb=bi&(bs<<(r+1));
bi=ba^(bb>>(r-l+1));
}
else{
bi.flip(q[i].x);
}
//cout<<bi<<endl;
}
L(i,1,n){
if(bi[i]){
ans^=a[i];//printf("%lld ",i);
}
}
printf("%lld\n",ans);
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll t=1;
bs=~bs;
scanf("%lld",&t);
while(t--)solve();
}
1001
题意：n个点，n-1条有向边，且所有点都可以到达点1。每次询问给出三个集合A,B,C，从A,B,C中分别选一个城市后，Alice从A中的城市出发到C中的城市，Bob从B中的城市到C中的城市，求有多少个城市Alice和Bob都会经过。
（题目读假了，没注意到有向边） 思路：很明显的树链剖分，以点1为根建树。因为是A->C,B->C，所以C一定是A,B的祖先。对于A中的每一个点a，标记树链1到a；对于B中的每一个点b，标记树链1到b；对于C中的每一个点c，标记以c为根的子树。最后查询只需询问有多少个点被abc都标记过了，线段树区间标记即可。
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,nz,ansx,ansy,lim,num,sum,pos,tot,root,block,key=1e9,cnt,mn,mx,ans;
ll a[N],head[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,sum[3];bool del,tag[3];}trs[N*4];
struct tree{ll fa,dep,dfn,siz,son,top,w;}tr[N];
struct edge{ll to,nxt;}eg[N*2];
bool cmp(qq u,qq v){
return u.x>v.x;
}
bool cmp1(qq u,qq v){
return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
return u>v;
}};//shun序
pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;
void add(ll u,ll v){
eg[++cnt].to=v;
eg[cnt].nxt=head[u];
head[u]=cnt;
}
void push_up(ll k){
L(i,0,2){
trs[k].sum[i]=trs[k*2].sum[i]+trs[k*2+1].sum[i];
}
}
void push_down(ll k){
ll l=k*2,r=k*2+1;
if(trs[k].del){
trs[l].del=1;trs[r].del=1;
L(i,0,2){
trs[l].sum[i]=0,trs[r].sum[i]=0;
trs[l].tag[i]=0,trs[r].tag[i]=0;
}
trs[k].del=0;
}
L(i,0,2){
trs[l].tag[i]|=trs[k].tag[i],trs[r].tag[i]|=trs[k].tag[i];
if(trs[k].tag[i]){
if(i==0)trs[l].sum[i]=trs[l].r-trs[l].l+1;
else trs[l].sum[i]=trs[l].sum[i-1];
if(i==0)trs[r].sum[i]=trs[r].r-trs[r].l+1;
else trs[r].sum[i]=trs[r].sum[i-1];
}
trs[k].tag[i]=0;
}
}
void bd_tree(ll k,ll l,ll r){
trs[k].del=0;
L(i,0,2)trs[k].tag[i]=0;
trs[k].l=l,trs[k].r=r;
if(l==r){
L(i,0,2)trs[k].sum[i]=0;
return;
}
ll mid=(l+r)/2;
bd_tree(k*2,l,mid);
bd_tree(k*2+1,mid+1,r);
push_up(k);
}
ll query(ll k,ll pl,ll pr){
ll ml=0,mr=0;
if(trs[k].l>=pl&&trs[k].r<=pr){
return trs[k].sum[2];
}
push_down(k);
ll mid=(trs[k].l+trs[k].r)/2;
if(mid>=pl)ml=query(k*2,pl,pr);
if(mid+1<=pr)mr=query(k*2+1,pl,pr);
return ml+mr;
}
void modify(ll k,ll pl,ll pr,ll p){
if(trs[k].l>=pl&&trs[k].r<=pr){
trs[k].tag[p]=1;
if(p==0)trs[k].sum[p]=trs[k].r-trs[k].l+1;
else trs[k].sum[p]=trs[k].sum[p-1];
return;
}
push_down(k);
ll mid=(trs[k].l+trs[k].r)/2;
if(mid>=pl)modify(k*2,pl,pr,p);
if(mid+1<=pr)modify(k*2+1,pl,pr,p);
push_up(k);
}
void del(){
L(i,0,2){
trs[1].sum[i]=0;
trs[1].tag[i]=0;
}
trs[1].del=1;
}
void dfs1(ll x,ll ac){
tr[x].fa=ac;
tr[x].dep=tr[tr[x].fa].dep+1;
tr[x].siz=1;
ll k=head[x];
while(k){
ll y=eg[k].to;
if(y!=ac){
dfs1(y,x);
tr[x].siz+=tr[y].siz;
if(!tr[x].son||tr[y].siz>tr[tr[x].son].siz)tr[x].son=y;
}
k=eg[k].nxt;
}
}
void dfs2(ll x,ll pos){
tr[x].dfn=++tot;
tr[x].top=pos;
if(!tr[x].son)return;
dfs2(tr[x].son,pos);
ll k=head[x];
while(k){
ll y=eg[k].to;
if(y!=tr[x].fa&&y!=tr[x].son)dfs2(y,y);
k=eg[k].nxt;
}
}
void mchain(ll x,ll y,ll p){
while(tr[x].top!=tr[y].top){
if(tr[tr[x].top].dep<tr[tr[y].top].dep)modify(1,tr[tr[y].top].dfn,tr[y].dfn,p),y=tr[tr[y].top].fa;
else modify(1,tr[tr[x].top].dfn,tr[x].dfn,p),x=tr[tr[x].top].fa;
}
if(tr[x].dep>tr[y].dep)swap(x,y);
modify(1,tr[x].dfn,tr[y].dfn,p);
}
void solve(){
scanf("%lld%lld",&n,&m);
cnt=0;tot=0;
L(i,1,n)head[i]=0;
L(i,2,n){
scanf("%lld",&x);
add(x,i);
}
dfs1(1,0);
dfs2(1,1);
bd_tree(1,1,n);//L(i,1,n)printf("%lld ",tr[i].dfn);printf("\n");
while(m--){
scanf("%lld%lld%lld",&nx,&ny,&nz);
L(i,1,nx){
scanf("%lld",&x);
mchain(1,x,0);
}
L(i,1,ny){
scanf("%lld",&x);
mchain(1,x,1);
}
L(i,1,nz){
scanf("%lld",&x);
modify(1,tr[x].dfn,tr[x].dfn+tr[x].siz-1,2);
}//L(i,1,n)printf("%lld ",query(1,i,i));
printf("%lld\n",query(1,1,n));
del();
}
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll t=1;
scanf("%lld",&t);
while(t--)solve();
}
京公网安备 11010502036488号