Paths on the Tree
贪心题，因为对于每一个儿子，经过的路径数之差少于 \(1\)，所以这道题可以理解为先把所有路径均分，然后把剩下的按照权值大小依次分布给那些儿子。
那么儿子传给父亲的权值又是如何处理呢？
首先，我们需要把父亲首先传递过来的 \(k\) 条路径均分，然后把剩下的最大路径给传递上去。
int n,m;
vector<int>g[N];
int ans=0,a[N];
inline int dfs(int u,int k){
ans+=k*a[u];
if(g[u].size()==0)return a[u];
int t=k/g[u].size(),res=k-t*g[u].size();
priority_queue<int>q;
for(auto v:g[u])q.push(dfs(v,t));
if(res){
while(res--){
ans+=q.top();
q.pop();
}
}
return q.top()+a[u];
}
inline void solve(){
n=read();m=read();
int x;
up(i,2,n){
x=read();
g[x].push_back(i);
}
up(i,1,n)a[i]=read();
dfs(1,m);
cout<<ans<<endl;
}
inline void clear(){
up(i,1,n)g[i].clear();
memset(a,0,sizeof a);
ans=0;
}
signed main(){
int T=read();
while(T--){
clear();
solve();
}
return 0;
}
Three Paths on a Tree
既然要求最长的并集，那么肯定有直径，然后再 bfs 出每个点离直径的距离。
注意，有可能第三个点并不存在，那么就选择直径上任意一个非端点的点。
int n,m,d;
int p[N];
vector<int>g[N];
int idx[N],cnt,a[N];
int dis1[N],dis2[N];
bool vis[N];
inline void dfs1(int u,int from){
dis1[u]=dis1[from]+1;
for(auto v:g[u]){
if(v==from)continue;
dfs1(v,u);
}
}
inline void dfs2(int u,int from){
for(auto v:g[u]){
if(v==from)continue;
dfs2(v,u);
if(vis[v])vis[u]=1;
}
}
int tmp,ans;
int L,R;
queue<int>q;
signed main() {
n=read();
int u,v;
up(i,1,n-1){
u=read();v=read();
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,0);
up(i,1,n)if(dis1[i]>dis1[L])L=i;
dfs1(L,0);
up(i,1,n)if(dis1[i]>dis1[R])R=i;
vis[L]=1;
dfs2(R,0);
memset(dis2,0x3f,sizeof dis2);
up(i,1,n)if(vis[i])q.push(i),dis2[i]=0;
while(q.size()){
int u=q.front();q.pop();
for(auto v:g[u]){
if(vis[v])continue;
dis2[v]=dis2[u]+1;
vis[v]=1;
q.push(v);
}
}
int T=0;
up(i,1,n){
if(ans<dis2[i]){
ans=dis2[i];
T=i;
}
}
if(T==0){
T++;
while(T==L||T==R)T++;
}
cout<<ans+dis1[R]-1<<endl;
cout<<L<<" "<<R<<" "<<T;
return 0;
}
Work Group
这个不是树上经典问题吗。
int n;
int val[N];
vector<int>g[N];
int f[N][2];
inline void dfs(int u){
f[u][1]=-inf;
for(auto v:g[u]){
dfs(v);
int x=f[u][0],y=f[u][1];
f[u][0]=max(f[v][0]+x,f[v][1]+y);
f[u][1]=max(f[v][1]+x,f[v][0]+y);
}
f[u][1]=max(f[u][1],f[u][0]+val[u]);
}
signed main(){
n=read();
int u,v;
up(i,1,n){
u=read();v=read();
if(u!=-1)g[u].push_back(i);
val[i]=v;
}
dfs(1);
cout<<max(f[1][0],f[1][1]);
return 0;
}
Paint the Tree
很有意思的一道树形 dp。
本来我先想了一个贪心，优先选取最大的边，然后依次满足条件，结果发现假了。
想一想 dp，令 \(f_{i,1}\) 表示以 \(i\) 为根的子树，能够和父亲连接上，\(f_{i,0}\) 则不能连接上。
先把所有不选的情况加上，然后用一个堆来替换，有点类似贪心的思想，注意一下，一个是前 \(k\) 个，一个是前 \(k-1\) 个。
int n,m,k;
vector<pii>g[N];
int f[N][2];
inline bool cmp(int x,int y){
return x>y;
}
inline void dfs(int u,int from){
vector<int>d;
for(auto i:g[u]){
int v=i.fi,w=i.se;
if(v==from)continue;
dfs(v,u);
f[u][0]+=f[v][0];
f[u][1]+=f[v][0];
d.push_back(f[v][1]+w-f[v][0]);
}
sort(d.begin(),d.end(),cmp);
for(int i=0;i<d.size()&&i<k;i++){
if(d[i]<=0)break;
if(i<k-1)f[u][1]+=d[i];
f[u][0]+=d[i];
}
}
inline void solve(){
n=read();k=read();
int u,v,w;
up(i,1,n-1){
u=read();v=read();w=read();
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dfs(1,0);
write(f[1][0],1);
}
inline void clear(){
up(i,1,n)g[i].clear();
up(i,1,n){
f[i][0]=0;
f[i][1]=0;
}
}
signed main(){
int T=read();
while(T--){
clear();
solve();
}
return 0;
}
Minimum spanning tree for each edge
先把最小生成树求出来，然后对于询问的边，如果它在生成树上，那么直接输出最小生成树，否则，与这条路径上的最大值替换。
用树链剖分轻松实现。
int n,m;
vector<pii>g[N];
struct treelca{
int siz[N],son[N],fa[N],dep[N],top[N];
int a[N];
inline void dfs1(int u,int from){
siz[u]=1;son[u]=0;
dep[u]=dep[from]+1;
for(auto [v,w]:g[u]){
if(v==from) continue;
a[v]=w;
fa[v]=u;dfs1(v,u);
if(siz[v]>siz[son[u]])son[u]=v;
siz[u]+=siz[v];
}
}
int idx[N],cnt,dfn[N];
inline void dfs2(int u,int tp){
top[u]=tp;idx[u]=++cnt;
dfn[cnt]=u;
if(son[u]!=0) dfs2(son[u],tp);
for(auto [v,w]:g[u]){
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
inline int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]])x=fa[top[x]];
else y=fa[top[y]];
}
return dep[x]<dep[y]?x:y;
}
int tr[N<<2];
inline void push_up(int k){
tr[k]=max(tr[lc],tr[rc]);
}
inline void build(int k=1,int l=1,int r=n){
if(l==r){
tr[k]=a[dfn[l]];
return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
push_up(k);
}
inline int ask(int x,int y,int k=1,int l=1,int r=n) {
if (x <= l && r <= y) return tr[k];
int mid=(l+r)>>1,res=0;
if (x<=mid)res=max(res,ask(x,y,lc,l,mid));
if (y>mid)res=max(res,ask(x,y,rc,mid+1,r));
return res;
}
inline int qmax(int x, int y) {
int res=0;
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x, y);
res=max(res,ask(idx[top[x]],idx[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x, y);
return max(res,ask(idx[x]+1,idx[y]));
}
}T;
struct edge{
int u,v,w,id;
}e[N<<1];
inline bool cmp(edge x,edge y){
return x.w<y.w;
}
inline bool cmp2(edge x,edge y){
return x.id<y.id;
}
int fa[N];
inline int find(int x){
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
bool vis[N];
signed main(){
n=read();m=read();
int u,v,w;
up(i,1,m){
e[i].u=read();
e[i].v=read();
e[i].w=read();
e[i].id=i;
}
sort(e+1,e+1+m,cmp);
int ans=0;
up(i,1,n)fa[i]=i;
up(i,1,m){
int fu=find(e[i].u),fv=find(e[i].v);
if(fu==fv)continue;
vis[e[i].id]=1;
fa[fu]=fv;
g[e[i].u].push_back({e[i].v,e[i].w});
g[e[i].v].push_back({e[i].u,e[i].w});
ans+=e[i].w;
}
T.dfs1(1,0);
T.dfs2(1,0);
T.build();
sort(e+1,e+1+m,cmp2);
up(i,1,m) {
if(vis[i])write(ans,1);
else write(ans+e[i].w-T.qmax(e[i].u,e[i].v),1);
}
return 0;
}
Paint the Tree
诈骗题，你以为是一一棵树，其实是一条链。
那么就可以直接枚举前两种颜色然后暴力。
但是某个 sb 还是写了树形 dp。
int n;
int c[4][N];
vector<int>g[N];
int deg[N],s;
int f[N][4][4],co[4][N],pre[N][4][4];
int a[N],len,ans,ansx,ansy,go,res[N];
inline void dfs(int u,int from){
a[++len]=u;
for(auto v:g[u]){
if(v==from)continue;
dfs(v,u);
}
}
signed main(){
n=read();
up(i,1,3){
up(j,1,n){
c[i][j]=read();
}
}
int u,v;
up(i,1,n-1){
u=read();v=read();
g[u].push_back(v);
g[v].push_back(u);
deg[u]++;deg[v]++;
}
int rt;
up(i,1,n){
if(deg[i]==1)rt=i;
else if(deg[i]>=3){
cout<<-1;
exit(0);
}
}
memset(f,0x3f,sizeof f);
dfs(rt,0);
up(i,1,3) {
up(j,1,3){
if(i==j)continue;
f[2][i][j]=min(f[2][i][j],c[i][a[1]]+c[j][a[2]]);
}
}
up(i,3,n){
up(j,1,3) {
up(k,1,3) {
up(t,1,3) {
if(j==k||j==t||k==t)continue;
if(f[i][k][t]>f[i-1][j][k]+c[t][a[i]]){
f[i][k][t]=f[i-1][j][k]+c[t][a[i]];
pre[i][k][t]=j;
}
}
}
}
}
ans=uinf;
up(i,1,3){
up(j,1,3){
if(f[n][i][j] < ans) {
ans=f[n][i][j];
ansx=i;ansy = j;
}
}
}
res[a[n-1]]=ansx;res[a[n]]=ansy;
for(register int i = n; i >= 3; i--) {
int go=pre[i][ansx][ansy];
ansy=ansx; ansx = go;
res[a[i-2]]=go;
}
cout<<ans<<endl;
up(i,1,n)cout<<res[i]<<" ";
return 0;
}