大型网站开发价格,wordpress调用 自定义php代码,极简个人网站模板,宣传手册设计模板正题
题目链接:https://www.luogu.com.cn/problem/P4383 题目大意 nnn个点的一棵树#xff0c;要求删除kkk条边然后接上kkk条边权为000的边后形成的树上选择一对(p,q)(p,q)(p,q)从ppp走简单路径到qqq的权值和最大。 n,k≤3105n,k\leq 3\times 10^5n,k≤3105 解题思路
其实可…正题
题目链接:https://www.luogu.com.cn/problem/P4383 题目大意
nnn个点的一棵树要求删除kkk条边然后接上kkk条边权为000的边后形成的树上选择一对(p,q)(p,q)(p,q)从ppp走简单路径到qqq的权值和最大。
n,k≤3×105n,k\leq 3\times 10^5n,k≤3×105 解题思路
其实可以理解为选恰好k1k1k1条不相交的路径可以选择一个点使得权值和最大这样删除路径最顶部的那条边一定有方案构造。
因为是恰好选择所以考虑wqswqswqs二分给每条路径加上一个权值midmidmid然后考虑用树形dpdpdp做就很简单了。设fi,0/1/2f_{i,0/1/2}fi,0/1/2表示iii号点没有路径经过/在路径之间/作为路径顶部时子树内的最小权值然后转移即可。
时间复杂度O(nlogW)O(n\log W)O(nlogW) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N3e510;
struct edge{ll to,next,w;
}a[N1];
struct node{ll w,g;
}f[N][3];
ll n,k,tot,c,ls[N];
node operator(node x,node y)
{return (node){x.wy.w,x.gy.g};}
node operator(node x,ll y)
{return (node){x.wy,x.g};}
node operator^(node x,ll y)
{return (node){x.w,x.gy};}
node mx(node x,node y){if(x.wy.w)return (x.gy.g)?x:y;return (x.wy.w)?x:y;
}
void addl(ll x,ll y,ll w){a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;return;
}
void dfs(ll x,ll fa){f[x][0]f[x][1](node){0,0};f[x][2](node){c,1};for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dfs(y,x);f[x][2]mx(f[x][2]f[y][0],(f[x][1]f[y][1]a[i].wc)^1);f[x][1]mx(f[x][0]f[y][1]a[i].w,f[x][1]f[y][0]);f[x][0]f[x][0]f[y][0];}f[x][0]mx(f[x][0],mx((f[x][1]c)^1,f[x][2]));return;
}
signed main()
{scanf(%lld%lld,n,k);ll sum0;k;for(ll i1;in;i){ll x,y,w;scanf(%lld%lld%lld,x,y,w);addl(x,y,w);addl(y,x,w);sumabs(w);}ll l-sum,rsum;while(lr){ll mid(lr)1;cmid;dfs(1,0);if(f[1][0].gk)lmid1;else rmid-1;}cl;dfs(1,0);printf(%lld\n,f[1][0].w-c*k);return 0;
}
