学校网站建设必要性,网站栏目变了怎么做跳转,网页设计师好吗,友情链接出售网正题
题目链接:https://www.luogu.com.cn/problem/P6776 题目大意
定义一次操作为将一棵树的叶子换成另一棵树。 定义一棵树TTT的grow(T)grow(T)grow(T)表示所有树TTT能够通过操作变成的树的集合。
现在给出mmm棵树TiT_iTi#xff0c;定义SSS为所有grow(Ti)grow(T_i)grow…正题
题目链接:https://www.luogu.com.cn/problem/P6776 题目大意
定义一次操作为将一棵树的叶子换成另一棵树。 定义一棵树TTT的grow(T)grow(T)grow(T)表示所有树TTT能够通过操作变成的树的集合。
现在给出mmm棵树TiT_iTi定义SSS为所有grow(Ti)grow(T_i)grow(Ti)的交集。
求SSS是否几乎完备指仅有有限棵树不在集合SSS内。
1≤∑n,∑m≤2×106,T≤1001\leq \sum n,\sum m\leq 2\times 10^6,T\leq 1001≤∑n,∑m≤2×106,T≤100 解题思路
我们考虑所有的树因为我们要细分到子树考虑所以这里考虑上空树中一个点可以到达所有非空树其他非空树都不能到达一个点而空树和一个点不能相互到达。
我们先把所有读入的树并起来然后每到一个点就分别考虑左右两边是否完备。
如果所有的树都存在一个点xxx使得左右两边都至少有两个点那么这棵树就没有作用了因为某一边一个点或者空树它们都到达不了那另一边就可以随便排了。
所以对于每个位置我们要保证左/右边为000个点和左/右边为111为一个点的树中在另一边都要是几乎完备的就合法了。
时间复杂度O(∑n)O(\sum n)O(∑n) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#includecctype
#define mp(x,y) make_pair(x,y)
#define ull unsigned long long
using namespace std;
const int N2e610;
const ull g131;
struct node{int id,x;node(int iid,int xx){idiid;xxx;return;}
};
const int o[2]{0,0};
int Case,n,m,cnt,t[N][2],siz[N];
ull pw[N];vectornodeq[N];
int read(){int x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-f;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
struct Tree{vectorint ch[2];vectorint siz;void build(int x,int p){if(!x)xcnt;if(ch[0][p])build(t[x][0],ch[0][p]);if(ch[1][p])build(t[x][1],ch[1][p]);siz[p]1siz[ch[0][p]]siz[ch[1][p]];return;}void init(int p){nread();siz.resize(n1);ch[0].resize(n1);ch[1].resize(n1);for(int i1;in;i)ch[0][i]read(),ch[1][i]read();int rt1;build(rt,1);q[1].push_back(node(p,1));}void Clear(){ch[0].clear();ch[1].clear();siz.clear();}bool isSon(int x){return (!ch[0][x]!ch[1][x]);}
}T[N];
bool solve(int x){for(int i0;iq[x].size();i)if(T[q[x][i].id].isSon(q[x][i].x))return 1;if(!q[x].size()||!t[x][0]||!t[x][1])return 0;bool ans1;for(int i0;iq[x].size();i){int idq[x][i].id,yq[x][i].x;if(T[id].siz[T[id].ch[1][y]]0T[id].ch[0][y])q[t[x][0]].push_back(node(id,T[id].ch[0][y]));}anssolve(t[x][0]);q[t[x][0]].clear();for(int i0;iq[x].size();i){int idq[x][i].id,yq[x][i].x;if(T[id].siz[T[id].ch[1][y]]1T[id].ch[0][y])q[t[x][0]].push_back(node(id,T[id].ch[0][y]));}anssolve(t[x][0]);q[t[x][0]].clear();for(int i0;iq[x].size();i){int idq[x][i].id,yq[x][i].x;if(T[id].siz[T[id].ch[0][y]]0T[id].ch[1][y])q[t[x][1]].push_back(node(id,T[id].ch[1][y]));}anssolve(t[x][1]);q[t[x][1]].clear();for(int i0;iq[x].size();i){int idq[x][i].id,yq[x][i].x;if(T[id].siz[T[id].ch[0][y]]1T[id].ch[1][y])q[t[x][1]].push_back(node(id,T[id].ch[1][y]));}anssolve(t[x][1]);q[t[x][1]].clear();return ans;
}
int main()
{
// freopen(surreal4.in,r,stdin);scanf(%d,Case);pw[0]1;for(int i1;iN;i)pw[i]pw[i-1]*g;while(Case--){for(int i1;icnt;i)q[i].clear(),t[i][0]t[i][1]0;for(int i1;im;i)T[i].Clear();cnt1;mread();for(int p1;pm;p)T[p].init(p);if(solve(1))puts(Almost Complete);else puts(No);}return 0;
}
