八大处做双眼预约网站,primitive technology wordpress,家装修效果图大全,公司网站一般是怎么做正题
题目链接:https://www.luogu.org/problem/P5024 题目大意
一棵树#xff0c;每次有要求 axby:a\ x\ b\ y:a x b y:表示aaa点是否必选和bbb点是否必选
然后每次求最小覆盖集。 解题思路
最小覆盖集全集-最大独立集 所以我们每次必选不选就用infinfinf或−inf-inf−inf…正题
题目链接:https://www.luogu.org/problem/P5024 题目大意
一棵树每次有要求 axby:a\ x\ b\ y:a x b y:表示aaa点是否必选和bbb点是否必选
然后每次求最小覆盖集。 解题思路
最小覆盖集全集-最大独立集 所以我们每次必选不选就用infinfinf或−inf-inf−inf处理即可 之后就是动态dp的模板了 https://blog.csdn.net/Mr_wuyongcong/article/details/95033161
但貌似树剖最后一个点会被卡飞吸口氧就莫得问题了(当然LCTLCTLCT也是没问题的) codecodecode
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize(Ofast)
%:pragma GCC optimize(inline)
%:pragma GCC optimize(-fgcse)
%:pragma GCC optimize(-fgcse-lm)
%:pragma GCC optimize(-fipa-sra)
%:pragma GCC optimize(-ftree-pre)
%:pragma GCC optimize(-ftree-vrp)
%:pragma GCC optimize(-fpeephole2)
%:pragma GCC optimize(-ffast-math)
%:pragma GCC optimize(-fsched-spec)
%:pragma GCC optimize(unroll-loops)
%:pragma GCC optimize(-falign-jumps)
%:pragma GCC optimize(-falign-loops)
%:pragma GCC optimize(-falign-labels)
%:pragma GCC optimize(-fdevirtualize)
%:pragma GCC optimize(-fcaller-saves)
%:pragma GCC optimize(-fcrossjumping)
%:pragma GCC optimize(-fthread-jumps)
%:pragma GCC optimize(-funroll-loops)
%:pragma GCC optimize(-fwhole-program)
%:pragma GCC optimize(-freorder-blocks)
%:pragma GCC optimize(-fschedule-insns)
%:pragma GCC optimize(inline-functions)
%:pragma GCC optimize(-ftree-tail-merge)
%:pragma GCC optimize(-fschedule-insns2)
%:pragma GCC optimize(-fstrict-aliasing)
%:pragma GCC optimize(-fstrict-overflow)
%:pragma GCC optimize(-falign-functions)
%:pragma GCC optimize(-fcse-skip-blocks)
%:pragma GCC optimize(-fcse-follow-jumps)
%:pragma GCC optimize(-fsched-interblock)
%:pragma GCC optimize(-fpartial-inlining)
%:pragma GCC optimize(no-stack-protector)
%:pragma GCC optimize(-freorder-functions)
%:pragma GCC optimize(-findirect-inlining)
%:pragma GCC optimize(-fhoist-adjacent-loads)
%:pragma GCC optimize(-frerun-cse-after-loop)
%:pragma GCC optimize(inline-small-functions)
%:pragma GCC optimize(-finline-small-functions)
%:pragma GCC optimize(-ftree-switch-conversion)
%:pragma GCC optimize(-foptimize-sibling-calls)
%:pragma GCC optimize(-fexpensive-optimizations)
%:pragma GCC optimize(-funsafe-loop-optimizations)
%:pragma GCC optimize(inline-functions-called-once)
%:pragma GCC optimize(-fdelete-null-pointer-checks)
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll Size2,N1e5100,inf(1ll60);
ll n,m,tot,cnt,ls[N],fa[N],v[N],f[N][2],sum;
ll seg[N],id[N],top[N],siz[N],son[N],ed[N];
struct matrix{ll a[Size][Size];
}val[N];
matrix operator*(matrix a,matrix b)
{matrix c;memset(c.a,0,sizeof(c.a));for(ll i0;iSize;i)for(ll j0;jSize;j)for(ll k0;kSize;k)c.a[i][j]max(c.a[i][j],a.a[i][k]b.a[k][j]);return c;
}
struct Tree_node{ll l,r;matrix g;
};
struct Edge_node{ll to,next;
}a[N1];
struct Line_cut_tree{Tree_node t[N2];void Build(ll x,ll l,ll r){t[x].ll;t[x].rr;if(lr){ll useg[l],g00,g1v[seg[l]];for(ll ils[u];i;ia[i].next){ll ya[i].to;if(yfa[u]||yson[u]) continue;g0max(f[y][0],f[y][1]),g1f[y][0];}t[x].g.a[0][0]t[x].g.a[0][1]g0;t[x].g.a[1][0]g1;val[l]t[x].g;return;}ll mid(lr)/2;Build(x*2,l,mid);Build(x*21,mid1,r);t[x].gt[x*2].g*t[x*21].g;}matrix Query(ll x,ll l,ll r){if(t[x].llt[x].rr)return t[x].g;if(t[x*2].rr) return Query(x*2,l,r);if(t[x*21].ll) return Query(x*21,l,r);return Query(x*2,l,t[x*2].r)*Query(x*21,t[x*21].l,r);}void Change(ll x,ll z){if(t[x].lt[x].r){t[x].gval[t[x].l];return;}if(t[x*2].rz) Change(x*2,z);else Change(x*21,z);t[x].gt[x*2].g*t[x*21].g;}
}Tree;
void addl(ll x,ll y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void dfs1(ll x,ll Fa)
{siz[x];fa[x]Fa;f[x][1]max(v[x],0ll);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yFa)continue;dfs1(y,x);f[x][0]max(f[y][0],f[y][1]);f[x][1]f[y][0];siz[x]siz[y];if(siz[y]siz[son[x]]) son[x]y;}
}
void dfs2(ll x,ll fa)
{id[x]cnt;seg[cnt]x;if(son[x]){top[son[x]]top[x];dfs2(son[x],x);}else ed[top[x]]cnt;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa||yson[x]) continue;top[y]y;dfs2(y,x);}
}
matrix ask(ll x)
{return Tree.Query(1,id[top[x]],ed[top[x]]);}
void path_change(ll x,ll w)
{val[id[x]].a[1][0]w-v[x];v[x]w;matrix old,news;while(x){oldask(top[x]);Tree.Change(1,id[x]);newsask(top[x]);xfa[top[x]];val[id[x]].a[0][0]max(news.a[0][0],news.a[1][0])-max(old.a[0][0],old.a[1][0]);val[id[x]].a[0][1]val[id[x]].a[0][0];val[id[x]].a[1][0]news.a[0][0]-old.a[0][0];}
}
int main()
{char rubbish[3];scanf(%lld%lld%s,n,m,rubbish);for(ll i1;in;i)scanf(%lld,v[i]),sumv[i];for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}top[1]1;dfs1(1,0);dfs2(1,0);Tree.Build(1,1,n);matrix ans;while(m--){ll a,x,b,y;scanf(%lld%lld%lld%lld,a,x,b,y);if(!x) path_change(a,v[a]inf);else path_change(a,v[a]-inf);if(!y) v[b],path_change(b,v[b]inf);else path_change(b,v[b]-inf);sum((x^1)(y^1))*inf;ansask(1);ll answersum-max(ans.a[0][0],ans.a[1][0]);if(answerinf) printf(-1\n);else printf(%lld\n,answer);if(!x) path_change(a,v[a]-inf);else path_change(a,v[a]inf);if(!y) v[b],path_change(b,v[b]-inf);else path_change(b,v[b]inf);sum-((x^1)(y^1))*inf;}
}
