梦熊NOIP模拟赛

T1

这道题贪心，实际上做了很久。
我们首先可以将4个相同的拆成3+1，这样是正确的。
然后我们就可以贪心枚举3+1，3+3+2，3+2，34，33，3*2，3这样的顺序来贪心。
最重要的是细节和顺序。
想出贪心策略后，这道题还是很简单的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
int a[5];
signed main() {
//	freopen("card4.in","r",stdin);int t=read();while(t--) {memset(a,0,sizeof a);int n=read();for(int i=1; i<=n; i++) {int v=read();a[3]+=v/3;v%=3;a[2]+=v/2;v%=2;a[1]+=v;}
//		cout<<a[1]<<"  "<<a[2]<<"  "<<a[3]<<endl;int ans=0;while(a[3]) {if(a[1]) {int res=min(a[1],a[3]);a[1]-=res;a[3]-=res;ans+=res;} else if(a[2]) {int res=min(a[2],a[3]/2);if(res==0) {a[3]--;a[1]++;a[2]--;ans+=1;} else {a[2]-=res;
//				a[1]++;a[3]-=res*2;ans+=res*2;}} else if(a[3]>=4) {int res=a[3]/4;a[3]-=res*4;ans+=3*res;} else {int res=a[3]/3;a[3]-=res*3;ans+=3*res;int rs=a[3]/2;a[3]-=rs*2;ans+=rs*2; ans+=a[3]*2;a[3]=0;
//				ans+=2;}
//			cout<<"OPOP"<<a[1]<<"  "<<a[2]<<"  "<<a[3]<<endl;
//			cout<<ans<<endl;}
//		cout<<a[1]<<"  "<<a[2]<<"  "<<a[3]<<endl;ans+=a[2];ans+=a[1];printf("%lld\n",ans);}return 0;
}

T2

这道题目和之前我出的题目有相似之处，都是用到了换根DP‘
首先我们先明确自己需要求什么，然后换根DP。
换根DP一般分为三个步骤，我在之前的博客中说到过，这里再写一遍。

先指定一个根节点
一次DFS统计子树内的节点对当前节点的贡献
一次DFS统计父亲节点对当前节点的贡献并合并统计最终答案。

然后看这道题目：
肯定会用到LCA，所以我们可以直接写出树上LCA的板子，然后分析这道题目：

考虑 z 距离 x 和 y 路径上最近的点为 p , 答案就是 $\max _{p \in \operatorname{dis}(x, y), z}\left\{c_{x}+c_{y}+c_{z}-\operatorname{dist}(x, y)-2 \operatorname{dist}(p, z)\right\}$ 。
可以拆贡献，设 $f_{u}=\max _{z}\left\{c_{z}-2 \operatorname{dist}(u, z)\right\}$ ，答案就是 $c_{x}+c_{y}-\operatorname{dist}(x, y)+\max _{p \in \operatorname{dis}(x, y)} f_{p}$ 。

如何做换根DP呢？

令 $dps_i$ 表示从父亲转移来的， $dpf_i$ 表示从其他子树转移来的。

第一次 dfs求出 $dps_i$ ，第二次 dfs求出 $dpf_i$ ，这就是换根了。
$dps_u = \max\{c_u, dps_v − 2w\}$
$dpf_v = \max\{c_v, dpf_u − 2w, dps_u − 2w\}$
然后这道题就可以写了：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
const int N=2e5+10;
int n,Q,fa[N][20],dep[N],lg[N];
int c[N],sum[N],sub[N],dp[N],mx[N][20];
struct edge{int v,nxt;int w;
}e[N<<1];
int hd[N],tt;
void init(){memset(hd,-1,sizeof(hd));for(int i=1;i<=n;i++)lg[i]=lg[i-1]+(1<<lg[i-1]==i);
}
void add(int x,int y,int z){e[++tt].v=y;e[tt].w=z;e[tt].nxt=hd[x];hd[x]=tt;
}
void dfs1(int u,int fath){sub[u]=c[u];for(int i=hd[u];~i;i=e[i].nxt){int v=e[i].v;if(v==fath) continue;sum[v]=sum[u]+e[i].w;dfs1(v,u);sub[u]=max(sub[u],sub[v]-2*e[i].w);}
}
void dfs2(int u,int fath){if(!fath) dp[u]=sub[u];for(int i=hd[u];~i;i=e[i].nxt){int v=e[i].v;if(v==fath) continue;dp[v]=max(sub[v],dp[u]-2*e[i].w);dfs2(v,u);}
}
void dfs(int u,int fath){fa[u][0]=fath,dep[u]=dep[fath]+1;mx[u][0]=max(dp[u],dp[fath]);for(int i=1;i<=lg[dep[u]];i++){fa[u][i]=fa[fa[u][i-1]][i-1];mx[u][i]=max(mx[fa[u][i-1]][i-1],mx[u][i-1]);}for(int i=hd[u];~i;i=e[i].nxt){int v=e[i].v;if(v!=fath) dfs(v,u);}
}
int lca(int x,int y){if(dep[x]<dep[y])swap(x,y);while(dep[x]>dep[y])x=fa[x][lg[dep[x]-dep[y]]-1];if(x==y) return x;for(int i=lg[dep[x]]-1;~i;i--){if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}}return fa[x][0];
}
int query(int u,int k){int ans=dp[u];for(int i=19;~i;i--){if(k&(1<<i)){ans=max(ans,mx[u][i]);u=fa[u][i];}}return ans;
}
int solve(int x,int z){int lc=lca(x,z);int xx=query(x,dep[x]-dep[lc]);int zz=query(z,dep[z]-dep[lc]);return c[x]+c[z]+max(xx,zz)-(sum[x]+sum[z]-2*sum[lc]);
}
signed main(){n=read(),Q=read();init();for(int i=1;i<=n;i++) c[i]=read();for(int i=1,x,y,z;i<n;i++){x=read(),y=read(),z=read();add(x,y,z),add(y,x,z);}dfs1(1,0),dfs2(1,0),dfs(1,0);for(int i=1,x,z;i<=Q;i++){x=read(),z=read();printf("%lld\n",solve(x,z));}return 0;
}