订正了三天的题目 自闭....
T1 幸福T2 树链剖分
考虑到 对于一个 树 确定覆盖哪几条边 不会随着 树的根节点的改变而改变
而且 这种对于一个无根树的路径进行覆盖 我们显然可以想到 树上差分 对于边的差分
对于一条路径从s到t 我们类比序列上的差分 即 $sum[s]--,sum[t]--,sum[lca(s,t)]-=2$
所以进行一遍dfs 求出一个节点的子树权值和 就是从这个点的父节点 到这个点 被覆盖了多少次
所以我们 求出所有的和就是整棵树所有边被覆盖的次数 记作res 然后单独考虑 这个树链剖分集合的大小
首先$size[i]$ 表示 i的子树和 那么就是$fa[i]$指向$i$那条边被覆盖的次数
$maxx[i]$ 表示从i出发的边中所有的儿子y 对应的最大的$size[y]$
$maxp[i]$ 表示从i出发的边中所有的儿子y 对应的次大的$size[y]$ 换根的时候会用到
然后考虑 对于一个节点来说 我们可以贪心的去选取 下一个 树链剖分的边 是指向哪个儿子的 显然是 当前被覆盖的边数次数最多的那一条边
这个贪心的正确性应该是显然的 所以我们考虑 指定不同的根节点 一定会造成不同的情况 这其中一定存在一个换根dp
我们按照刚才贪心的思路 我们可以求出来 以当前为根的子树内最大树链剖分的大小 指定1为根节点 显然存在$g[1]=所有节点的maxx[i]$
假设当前存在一条从x指向y的边 而且 $g[x]$ 已经求出 我们现在考虑 怎么求出来$g[y]$
存在状态转移方程:
$$g[y]=g[x]-max(size[x],maxx[x])-maxx[y];$$
$$g[y]+=max(size[y],maxx[y])+max(size[x],size[y]==maxx[x]?maxp[x]:maxx[x]);$$
对于第二个方程 是因为 我们需要知道x有没有选择指向y的那条边 如果选择的是y 那么 我们就要加上x出发的次大值 否则
我们就要加上最大值 此时y成为了整颗子树的根 而对于他的儿子他只能选择一条边 我们按照贪心的思路就找都这条边
#include<bits/stdc++.h> using namespace std; template<typename T>inline void read(T &x) { x=0;T f=1,ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x*=f; } typedef long long ll; const int N=100010; ll n,m,tot,x,y,size[N],sum[N],d[N],f[N][25],lin[N]; ll g[N];//f1[i]表示以i为根的子树内的最大树链剖分 //g[i] 表示以i为整颗子树的根的最大树链剖分 ll res,maxx[N],maxp[N],sx[N],sxp[N]; struct gg { int y,next; }a[N<<1]; inline void add(ll x,ll y) { a[++tot].y=y; a[tot].next=lin[x]; lin[x]=tot; } inline void bfs() { queue<ll>q; q.push(1);d[1]=1; while(q.size()) { ll x=q.front(); q.pop(); for(ll i=lin[x];i;i=a[i].next) { ll y=a[i].y; if(d[y]) continue; d[y]=d[x]+1; f[y][0]=x; for(int j=1;j<=23;j++) f[y][j]=f[f[y][j-1]][j-1]; q.push(y); } } } inline ll lca(ll x,ll y) { if(d[x]>d[y]) swap(x,y); for(ll i=23;i>=0;--i) { if(d[f[y][i]]>=d[x]) y=f[y][i]; } if(x==y) return x; for(ll i=23;i>=0;--i) { if(f[y][i]!=f[x][i]) { y=f[y][i],x=f[x][i]; } } return f[x][0]; } inline void dfs(ll x,ll fa) { size[x]=sum[x]; for(ll i=lin[x];i;i=a[i].next) { ll y=a[i].y; if(y==fa) continue; dfs(y,x); size[x]+=size[y]; if(maxx[x]<size[y]) { maxp[x]=maxx[x]; maxx[x]=size[y]; } else if(size[y]>maxp[x]) { maxp[x]=size[y]; } } g[1]+=maxx[x];res+=size[x]; } inline void dp(ll x,ll fa) { for(ll i=lin[x];i;i=a[i].next) { ll y=a[i].y; if(y==fa) continue; g[y]=g[x]-max(size[x],maxx[x])-maxx[y]; g[y]+=max(size[y],maxx[y])+max(size[x],size[y]==maxx[x]?maxp[x]:maxx[x]); dp(y,x); } } int main() { //freopen("1.in.cpp","r",stdin); read(n); read(m); for(ll i=1;i<n;i++) { read(x); read(y); add(x,y); add(y,x); } bfs(); for(ll i=1;i<=m;i++) { read(x); read(y); sum[x]++,sum[y]++; ll c=lca(x,y); sum[c]-=2; } dfs(1,0); dp(1,0); ll ans=0,x; for(ll i=1;i<=n;i++) { if(ans<g[i]) { //x=i; ans=g[i]; } } cout<<res-ans<<endl; return 0; }View Code
T3
比较自闭的是 我以为分给小Ex张 而将剩下y张都给了小y
算了 这不重要 我们存在一种暴力的做法 就是枚举出来当前小E 手中每种i花色牌的数量 然后考虑对于他拥有的第i个花色的牌的数量bi
但是这样的情况过多 所以我们不妨枚举胜率 还是对于第i种花色 考虑此时小E手中拥有bi 然后考虑 此时小E选择 i花色 能赢的概率
那么此时 设小F拥有的 i 花色的牌的数量是 j 那么存在 可以使小E 获胜的方案数
$\sum_{j=0}^{min{y,b_i-a_i,b_i-z}}\binom{a_i-b_i}{j}\binom{m-x-a_i+b_i}$