滨州改版网站建设服务,wordpress会员下载功能,建筑网站推荐,网站推广优化服务正题
题目链接:https://www.luogu.com.cn/problem/CF566E 题目大意
有一棵树#xff0c;但是你不知道它的形态。你现在只知道距离每个点距离不超过222的点集#xff0c;但是你不知道每个点集是对应哪个点的。
现在要你求这棵树。 2≤n≤10002\leq n\leq 10002≤n≤1000 解…正题
题目链接:https://www.luogu.com.cn/problem/CF566E 题目大意
有一棵树但是你不知道它的形态。你现在只知道距离每个点距离不超过222的点集但是你不知道每个点集是对应哪个点的。
现在要你求这棵树。
2≤n≤10002\leq n\leq 10002≤n≤1000 解题思路
考虑这样一种情况 那么???和?′??′的交集恰好是xxx和yyy也就是所有非叶子的连边我们都可以用以上方式确定。
然后考虑怎么确定叶子的连边对于叶子xxx来说包含它的集合中最小的那个肯定是它自己的集合。
这样我们就可以确定每个叶子对应的集合了然后考虑怎么求它的父亲。
会发现我们如果把叶子的集合中的叶子去掉那就只剩下它的父节点和它父节点连接的其他非叶子节点。
我们再处理出一个非叶子节点连边的集合然后一个一个比较就可以找到这个点的父亲了。
然后要特判一些情况
没有非叶子节点此时n2n2n2直接特判。只有一个非叶子节点此时随便找一个点都可以当非叶子节点。只有两个非叶子节点此时叶子的集合分两种情况分别对应不同的父节点就好了。
用bitsetbitsetbitset优化即可做到O(n3ω)O(\frac{n^3}{\omega})O(ωn3) code
#includecstdio
#includecstring
#includealgorithm
#includebitset
#includevector
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N1050;
int n,k[N],f[N];;
bitsetN b[N],g[N],c,v;
vectorpairint,int e;
int main()
{scanf(%d,n);for(int i0;in;i)f[i]n,g[i][i]1;k[n]n1;if(n2)return puts(1 2)0;for(int i0;in;i){scanf(%d,k[i]);for(int j1,x;jk[i];j){scanf(%d,x);x--;b[i][x]1;f[x](k[i]k[f[x]])?i:f[x];}}for(int i0;in;i)for(int ji1;jn;j){cb[i]b[j];if(c.count()2){int ac._Find_first();int bc._Find_next(a);e.push_back(mp(min(a,b),max(a,b)));g[a][b]g[b][a]v[a]v[b]1;}}if(v.count()0){for(int i1;in;i)printf(%d %d\n,i1,1);return 0;}else if(v.count()2){int pv._Find_first();int qv._Find_next(p);printf(%d %d\n,p1,q1);bool flag0;for(int i0;in;i)if(!v[i]){if(flag){if(b[f[i]]c)printf(%d %d\n,i1,p1);else printf(%d %d\n,i1,q1);}else printf(%d %d\n,i1,p1),cb[f[i]],flag1;}return 0;}for(int i0;in;i){if(v[i])continue;b[f[i]]v;for(int j0;jn;j)if(b[f[i]]g[j]){e.push_back(mp(min(i,j),max(i,j)));break;}}sort(e.begin(),e.end());for(int i0;ie.size();i)if(!i||e[i]!e[i-1])printf(%d %d\n,e[i].first1,e[i].second1);return 0;
}