鹤壁高端网站建设,泰安网络营销,t型布局网站的优缺点,电脑网页翻译Problem - E - Codeforces
题意#xff1a; 思路#xff1a;
注意到题目的性质#xff1a;满足条件的路径个数是极少的#xff0c;因为每个点离路径的距离1
先考虑一条链#xff0c;那么直接就选最深那个点作为端点即可
为什么#xff0c;因为我们需要遍历所有点…Problem - E - Codeforces
题意 思路
注意到题目的性质满足条件的路径个数是极少的因为每个点离路径的距离1
先考虑一条链那么直接就选最深那个点作为端点即可
为什么因为我们需要遍历所有点的父亲
推广到树也是要遍历所有点的父亲 Code
#include bits/stdc.h#define int long longusing namespace std;const int mxn2e510;
const int mod1e97;vectorint G[mxn];int N,M,K,u,v,x;
int idx0;
int dep[mxn],In[mxn],sz[mxn],F[mxn];void dfs(int u,int fa){sz[u]1;F[u]fa;dep[u]dep[fa]1;In[u]idx;for(auto v:G[u]){if(vfa) continue;dfs(v,u);sz[u]sz[v];}
}
bool cmp(int x,int y){return dep[x]dep[y];
}
bool check(int u,int v){return In[v]In[u]In[v]In[u]sz[u]-1;
}
void init(){for(int i0;iN;i){dep[i]In[i]sz[i]F[i]0;G[i].clear();}
}
void solve(){cinNM;init();for(int i1;iN-1;i){cinuv;G[u].push_back(v);G[v].push_back(u);}dfs(1,0);F[1]1;while(M--){cinK;vectorint V;for(int i1;iK;i){cinx;V.push_back(F[x]);}//for(int i0;iV.size();i) coutV[i] \n[iV.size()-1];sort(V.begin(),V.end(),cmp);int ok1;for(int i1;iV.size();i){if(!check(V[i-1],V[i])){ok0;break;} }if(ok) coutYES\n;else coutNO\n;}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __1;//cin__;while(__--)solve();return 0;
}
