首页 > 其他分享 >Codeforces Round #722 C

Codeforces Round #722 C

时间:2022-10-18 14:15:52浏览次数:44  
标签:const int Codeforces 节点 abs 722 av Round dp

C. Parsa's Humongous Tree

显然可以证明我们的每一个节点肯定是会取到边界值才是最优解
比如 我们当前其他节点确定
我们中间节点v不确定 我们让av从lv开始
av++ 如果旁边节点的数大于av的较多 我们贡献减少 如果旁边节点的数大于av的较少我们的贡献增加
显然这是一个单峰函数
我们显然只能在旁边两个点取到极值
然后我们可以想到的就是直接大小大小这样填
显然这样是不合理的 所以我们dp
我们显然对于lr需要一个状态 然后就是类似树形dp
dp[i][0/1]表示i子树的ai选li还是ri的max
转移就很简单了 直接暴力A22

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int n,dp[N][2],l[N],r[N];
vector<int>g[N];
void dfs(int u,int fa){
    for(auto v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
        dp[u][0]+=max(dp[v][0]+abs(l[u]-l[v]),dp[v][1]+abs(l[u]-r[v]));
        dp[u][1]+=max(dp[v][0]+abs(r[u]-l[v]),dp[v][1]+abs(r[u]-r[v]));
    }
}
void solve() {
    cin>>n;
    for(int i=1;i<=n;i++)g[i].clear(),dp[i][0]=dp[i][1]=0;
    for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    cout<<max(dp[1][0],dp[1][1])<<endl;
}
signed main(){
    fast
    int t;t=1;cin>>t;
    while(t--) {
        solve();
    }
    return ~~(0^_^0);
}

标签:const,int,Codeforces,节点,abs,722,av,Round,dp
From: https://www.cnblogs.com/ycllz/p/16802347.html

相关文章

  • 8. CSS background(背景)
    1.前言在制作网页时我们往往需要在网页中添加一些背景颜色、背景图像让网页更加美观,吸引访问者的眼球。CSS中提供了一系列用于设置HTML元素背景效果的属性,如下所示:b......
  • AspectJ中JoinPoint和ProceedingJoinPoint注解的使用,ProceedingJoinPoint只能用在arou
    AspectJ中JoinPoint和ProceedingJoinPoint注解的使用,ProceedingJoinPoint只能用在around(环绕通知)中环绕通知=前置+目标方法执行+后置通知,proceed方法就是用于启动目标方......
  • Codeforces Round #828 (Div. 3) E2 // 数论 + dfs
    题目来源:CodeforcesRound#828(Div.3)E2-DivisibleNumbers题目链接:Problem-E2-Codeforces题意有\(t\)组案例(\(1\\let\le10\)),对于每个案例:给定四个整......
  • Codeforces Round #733 D
    D.SecretSanta答案就是每一个数字是否出现很容易想到的就是我们只能满足一个人的要求(如果这一组人都选择同一个人所以我们直接就这样乱搞就可以了然后剩下的随便连一......
  • Codeforces Global Round 23 -D.Paths on the Tree
    题意给定一个树,树上每个节点i有一个权值s[i]。一共有k条从1(一定是根节点)开始的简单路径。设i点有c条路径通过,则其总权值为c*s.现在在限制:如果p[u]=i,p[v]=i,则abs(c[u]......
  • Codeforces Round #726 E1
    E1.EraseandExtend(EasyVersion)首先我们来证一个东西就是最优解一定由先删若干次然后一直copy而来而不会在中途再删一次因为在中途再删一次就证明这个后缀不如前......
  • Codeforces Round #828 (Div. 3)
    CodeforcesRound#828(Div.3)https://codeforces.com/contest/1744罚时爆炸的a~e1A.NumberReplacement数字一样的对应字母一定要一样#include<bits/stdc++.h>......
  • Codeforces Round #827 (Div. 4) 复盘+题解
    原比赛链接复盘:ABC签到,手速太慢了。D捣鼓了好久才想起来从更小的值域出发去做。E简单二分答案。然后就timeout了。D题搞错方向浪费太久时间了。F思维题,拐两个弯再$r......
  • Codeforces Round #729 (Div. 2) C
    C.StrangeFunction考虑反想我们将x确定看看有多少个i对于f[i]=x我们显然i%lcm(1,2,3,...x-1)!=0这里就可以通过容斥直接求解i%lcm(1,2,3,...x-1)是含有1,2,3,...x-1......
  • Educational Codeforces Round 112 D
    D.SayNotoPalindromes很牛逼我们手动模拟一下可以知道只有3个字母不构成回文串只有可能是这样的abcabc....acbacb.......6种情况所以直接暴力预处理即可#inclu......