首页 > 其他分享 >2022 CCPC 广州站 Alice and Her Lost Cat

2022 CCPC 广州站 Alice and Her Lost Cat

时间:2022-11-14 18:59:16浏览次数:61  
标签:bg chd Her Lost min int CCPC mx1 bagg

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 #define rg register
  4 #define ll long long
  5 #define ld long double
  6 #define FOR(i,a,b) for(register int i=a;i<=b;++i)
  7 #define For(i,a,b) for(register int i=a;i>=b;--i)
  8 static char buf[100000],*pa(buf),*pb(buf);
  9 inline int rd();inline void wrt(int x);inline ll rdll();inline void wrtll(ll x);
 10 #define gc getchar()
 11 const ll INF=1E+17,modd=998244353,N=2E+3+10;
 12 
 13 int T,n,fa[N],mx1[N];
 14 ll a[N],t[N],f[N][N][2],bagg[N],bg[N][2],ans;
 15 vector<int> chd[N],cd[N];
 16 bool vis[N],vis1[N];
 17 
 18 void ps(int u)
 19 {
 20     vis1[u]=1;
 21     FOR(i,0,int(cd[u].size())-1)
 22     {
 23         int v=cd[u][i];
 24         if(vis1[v])
 25         {
 26             chd[v].push_back(u);
 27             fa[u]=v;
 28         }
 29         else ps(v);
 30     }
 31 }
 32 
 33 void doo(int u)
 34 {
 35     vis[u]=1;
 36     if(chd[u].size()==0)
 37     {
 38         f[u][0][1]=0;
 39         f[u][0][0]=a[u];
 40         f[u][1][0]=0;
 41         mx1[u]=1;return;
 42     }
 43     FOR(i,0,int(chd[u].size())-1)
 44     {
 45         int v=chd[u][i];
 46         if(!vis[v]) doo(v);
 47         mx1[u]+=mx1[v];
 48     }
 49     //bb1
 50     memset(bagg,3,sizeof(bagg));bagg[0]=0;
 51     FOR(i,0,int(chd[u].size())-1) For(j,mx1[u],0) 
 52     {
 53         bagg[j]=bagg[j]+f[chd[u][i]][0][0];
 54         FOR(k,1,j)
 55             bagg[j]=min(bagg[j],bagg[j-k]+f[chd[u][i]][k][0]);
 56     }
 57     FOR(i,0,mx1[u]) f[u][i][0]=min(f[u][i][0],bagg[i]);
 58     //bb2
 59     memset(bagg,3,sizeof(bagg));bagg[0]=0;
 60     FOR(i,0,int(chd[u].size())-1) For(j,mx1[u],0) 
 61     {
 62         bagg[j]=bagg[j]+min(f[chd[u][i]][0][0],f[chd[u][i]][0][1]);
 63         FOR(k,1,j)
 64             bagg[j]=min(bagg[j],bagg[j-k]+min(f[chd[u][i]][k][0],f[chd[u][i]][k][1]));
 65     }
 66     FOR(i,0,mx1[u]) f[u][i][0]=min(f[u][i][0],bagg[i]+a[u]);
 67     //bb3
 68     memset(bg,3,sizeof(bg));bg[0][0]=0;
 69     FOR(i,0,int(chd[u].size())-1) For(j,mx1[u],0) 
 70     {
 71         bg[j][1]=min(bg[j][1]+f[chd[u][i]][0][0],bg[j][0]+f[chd[u][i]][0][1]);
 72         bg[j][0]=bg[j][0]+f[chd[u][i]][0][0];
 73         FOR(k,1,j)
 74             bg[j][1]=min(bg[j][1],bg[j-k][0]+f[chd[u][i]][k][1]),
 75             bg[j][1]=min(bg[j][1],bg[j-k][1]+f[chd[u][i]][k][0]),
 76             bg[j][0]=min(bg[j][0],bg[j-k][0]+f[chd[u][i]][k][0]);
 77     }
 78     FOR(i,0,mx1[u]) f[u][i][1]=min(f[u][i][1],min(bg[i][0],bg[i][1]));
 79     return;
 80 }
 81 
 82 int main()
 83 {
 84     T=rd();while(T--){
 85     memset(f,3,sizeof(f));
 86     ans=INF;
 87     memset(mx1,0,sizeof(mx1));
 88     memset(vis,0,sizeof(vis));
 89     memset(vis1,0,sizeof(vis1));
 90     //f0
 91     n=rd();
 92     FOR(i,1,n) chd[i].clear(),cd[i].clear();
 93     //FOR(i,1,n) cout<<chd[i].size()<<" ";cout<<endl;
 94     FOR(i,1,n) a[i]=rdll();
 95     FOR(i,1,n) t[i]=rdll();
 96     FOR(i,1,n-1) 
 97     {
 98         int u=rd(),v=rd();
 99         cd[u].push_back(v);
100         cd[v].push_back(u);
101     }
102     ps(1);
103     doo(1);
104     FOR(i,0,mx1[1]) ans=min(ans,t[i]+min(f[1][i][0],f[1][i][1]));
105     cout<<ans<<endl;
106     }return 0;
107 }
108 inline int rd()
109 {
110     register int x(0);register char c(gc);bool bbb=1;
111     if(c=='-') {bbb=0;c=gc;}
112     while(c<'0'||c>'9')c=gc;
113     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc;
114     if(bbb)return x;else return -x;
115 }
116 inline ll rdll()
117 {
118     register ll x(0);register char c(gc);bool bbb=1;
119     if(c=='-') {bbb=0;c=gc;}
120     while(c<'0'||c>'9')c=gc;
121     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc;
122     if(bbb)return x;else return -x;
123 }

 

标签:bg,chd,Her,Lost,min,int,CCPC,mx1,bagg
From: https://www.cnblogs.com/universeplayer/p/16889967.html

相关文章

  • Manacher
    通过在字符串之间的每个空位内插入字符,是的奇数和偶数成为一样得情况,从而能够统一处理。用len[]记录每个点能够扩展出的最长半径,mx记录扩展到的最远右端点,id记录mx为右端......
  • rancher prometheus监控API未就绪
    目录rancherprometheus监控API未就绪背景问题排查问题解决rancherprometheus监控API未就绪背景rancher在应用商店部署了自带的prometheus后,由于闲杂人员比较多,发现监......
  • 2022 China Collegiate Programming Contest (CCPC) Weihai Site
    比赛链接:https://codeforces.com/gym/104023A.Dunai题意:\(n\)个队伍获得过冠军,告知每个队伍中的人及对应的位置,现在已知\(m\)个选手及它们的位置,问能组成多少个五......
  • Linux系统出现cannot create temp file for here-document: Read-only file system解
    打开终端输入命令比如mkdir、cd等等,会出现如下提示cannotcreatetempfileforhere-document:Read-onlyfilesystem解决办法如下:mount-oremount,rw/原文:https:......
  • Codeforces 722 F Cyclic Cipher 题解 (同余方程,two-pointers)
    题目链接前两天做过一个题意类似但做法不类似的题在这里首先做这道题需要一个结论:(一元)同余方程组有解的充要条件是方程组中的所有方程两两联立有解。证明两个同......
  • Use Where Clause With Merge
    UseWhereClauseWithMerge ThereisnoWHEREinthatpartoftheMERGEstatement.SeeMERGE(Transact-SQL)inthedocumentationforsyntaxhelp.Thereis......
  • 说说Vue响应式系统中的Watcher和Dep的关系-面试进阶
    引言在这里我先提出两个问题(文章末尾会进行解答):在Vue的数据响应系统中,Dep和Watcher各自分担什么任务?Vue的数据响应系统的核心是Object.defineproperty一定是最好的吗?有......
  • K8s系列---【KubeSphere配置应用商店的仓库地址】
    KubeSphere配置应用商店的仓库地址1.找到提供chart的helm仓库https://helm.sh/随便搜索一个chart,例如redis,找到bitnami的url"https://charts.bitnami.com/bitnami" ......
  • 2022.11.13:CCPC广州
    补题传送门3题铁这把铁没有沈阳铜那么不甘心(沈阳打完之后,一星期都睡不好),看到了队伍内很多知识点的缺失,不知道在剩下一个正式赛来之前能不能弥补上(跟去年一样,做北大出的......
  • 22.11.13 CCPC 广州站 记录
    上来看A(树上DP),直观认为可做,前后拉着队友研究了两个小时,经过lcx,lgy两次hack正确性,最终基本得到答案思路,因为过于复杂和担心正确性问题不敢写。反思:1.正式比赛中不应该一开......