网站开发的微端是什么,毕业设计做视频网站设计,山东省农村电影监控平台下载,制作网站软件下载正题
题目链接:https://www.luogu.com.cn/problem/P6773 题目大意 nnn个点的一棵树#xff0c;边权可以是000或111。mmm个条件(x,y)(x,y)(x,y)表示要求x,yx,yx,y之间要有边权值为111#xff08;保证xxx是yyy的祖先#xff09;#xff0c;求方案数。 解题思路
考虑容斥边权可以是000或111。mmm个条件(x,y)(x,y)(x,y)表示要求x,yx,yx,y之间要有边权值为111保证xxx是yyy的祖先求方案数。 解题思路
考虑容斥首先我们把没有用的条件去掉就是被其他条件包含的如果有kkk条路径上没有111那么容斥系数为∣−1∣k|-1|^k∣−1∣k。
设fi,jf_{i,j}fi,j表示点iii的子树中要再往上到深度为jjj的节点都不能是111时的答案那么有转移方程fx,min{j,k}fx,j∗fy,kf_{x,min\{j,k\}}f_{x,j}*f_{y,k}fx,min{j,k}fx,j∗fy,k 这是一个min−maxmin-maxmin−max卷积的形式用线段树合并维护即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N5e510,XJQ998244353;
struct node{ll to,next;
}a[N*2];
ll n,m,tot,ls[N],dep[N],rt[N],up[N];
struct Seq_Tree{ll cnt,w[N6],ls[N6],rs[N6],lazy[N6];void Downdata(ll x){if(lazy[x]1)return;w[ls[x]]w[ls[x]]*lazy[x]%XJQ;w[rs[x]]w[rs[x]]*lazy[x]%XJQ;lazy[ls[x]]lazy[ls[x]]*lazy[x]%XJQ;lazy[rs[x]]lazy[rs[x]]*lazy[x]%XJQ;lazy[x]1;return;}void Insert(ll x,ll L,ll R,ll pos,ll val){if(!x)xcnt,lazy[x]1;if(LR){w[x]val;return;}ll mid(LR)1;Downdata(x);if(posmid)Insert(ls[x],L,mid,pos,val);else Insert(rs[x],mid1,R,pos,val);w[x](w[ls[x]]w[rs[x]])%XJQ;return;}void Change(ll x,ll L,ll R,ll l,ll r){if(!x)xcnt,lazy[x]1;if(LlRr){lazy[x]lazy[x]*2%XJQ;w[x]w[x]*2%XJQ;return;}ll mid(LR)1;Downdata(x);if(rmid)Change(ls[x],L,mid,l,r);else if(lmid)Change(rs[x],mid1,R,l,r);else Change(ls[x],L,mid,l,mid),Change(rs[x],mid1,R,mid1,r);w[x](w[ls[x]]w[rs[x]])%XJQ;return;}ll Merge(ll x,ll y,ll l,ll r,ll w1,ll w2){if(!x||!y){w[x]w[x]*w2%XJQ;lazy[x]lazy[x]*w2%XJQ;w[y]w[y]*w1%XJQ;lazy[y]lazy[y]*w1%XJQ;return xy;}if(lr){w[x](w[x]*w[y]w[x]*w2w[y]*w1)%XJQ;return x;}ll mid(lr)1;Downdata(x);Downdata(y);ls[x]Merge(ls[x],ls[y],l,mid,(w1w[rs[x]])%XJQ,(w2w[rs[y]])%XJQ);rs[x]Merge(rs[x],rs[y],mid1,r,w1,w2);w[x](w[ls[x]]w[rs[x]])%XJQ;return x; }
}T;
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(ll x,ll fa){dep[x]dep[fa]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dfs(y,x);}return;
}
void solve(ll x,ll fa){if(up[x])T.Insert(rt[x],1,n,up[x],XJQ-1);T.Insert(rt[x],1,n,n,1);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;solve(y,x);T.Change(rt[y],1,n,dep[y],n);rt[x]T.Merge(rt[x],rt[y],1,n,0,0);}
// printf(%d\n,T.w[rt[x]]);return;
}
int main()
{scanf(%lld,n);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}dfs(1,0);scanf(%lld,m);while(m--){ll x,y;scanf(%lld%lld,x,y);up[y]max(up[y],dep[x]);}solve(1,0);printf(%lld,T.w[rt[1]]);return 0;
}
