宿迁哪里有做网站开发的,wordpress mysql权限设置,泉州网站建设qzdzi,wordpress 3.5 漏洞 xss正题
题目链接:https://www.luogu.com.cn/problem/P7011 题目大意
给出nnn个点的一棵树#xff0c;从一出发#xff0c;要走到 ttt。初始时权值为000#xff0c;每个节点有一个权值wiw_iwi#xff0c;第一次走过这个节点时会让权值加上该节点的权值#xff0c;要求全程…正题
题目链接:https://www.luogu.com.cn/problem/P7011 题目大意
给出nnn个点的一棵树从一出发要走到 ttt。初始时权值为000每个节点有一个权值wiw_iwi第一次走过这个节点时会让权值加上该节点的权值要求全程权值不能为负数求能否走到ttt。
1≤n≤2×1051\leq n\leq 2\times 10^51≤n≤2×105 解题思路
第一个比较麻烦的点是有一个终点的限制我们走到终点之后就不需要考虑其他点了不妨在终点后接一个权值为∞\infty∞的节点然后问题变为能否遍历全树。
接下来我们会发现有个很麻烦的点因为对于一个子树我们可能进入多次一个比较暴力的想法是我们可以设fx,jf_{x,j}fx,j表示我们在权值为jjj的时候进入xxx的子树再出来时能够变为的最大权值。
假设我们权值从jjj增加到了jkjkjk那么再进入能够获得的贡献就是fi,jk−fi,jf_{i,jk}-f_{i,j}fi,jk−fi,j不难发现对于一个fi,jf_{i,j}fi,j不同的权值个数只有最多子树大小个。考虑维护这些变换的位置记为若干个二元组(x,y)(x,y)(x,y)表示权值为xxx时进入能够获得yyy的权值显然的我们有这些区间[x,xy][x,xy][x,xy]是不相交的因为如果相交那么可以一次获得更多权值。
而合并的时候我们直接暴力把这些区间合并因为即使表现上相交了我们可以后续考虑节点权值的时候再合并这些区间然后根据节点xxx的权值暴力合并前面的区间。
至于两个堆的合并自然可以用可并堆但是不如启发式合并好写。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) code
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define ll long long
#define mp(x,y) make_pair(x,y)
using namespace std;
const ll N2e510;
struct node{ll to,next;
}a[N1];
ll T,n,t,tot,ls[N],p[N],w[N];
priority_queuepairll,ll q[N];
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(ll x,ll fa){p[x]x;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dfs(y,x);if(q[p[y]].size()q[p[x]].size())swap(p[x],p[y]);while(!q[p[y]].empty()){q[p[x]].push(q[p[y]].top());q[p[y]].pop();}}pairll,ll kmp(0,w[x]);while(!q[p[x]].empty()){pairll,ll zq[p[x]].top();z.first-z.first;if(k.second0z.firstk.firstk.second)break;kmp(max(k.first,z.first-k.second),k.secondz.second);q[p[x]].pop();}k.first-k.first;if(k.second0)q[p[x]].push(k);return;
}
signed main()
{scanf(%lld,T);while(T--){scanf(%lld%lld,n,t);tot0;for(ll i1;in1;i){ls[i]0;while(!q[i].empty())q[i].pop();}for(ll i1;in;i)scanf(%lld,w[i]);for(ll i1,x,y;in;i){scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}n;w[n]1e18;addl(t,n);addl(n,t);dfs(1,0);if(q[p[1]].empty())puts(trapped);else{pairll,ll wq[p[1]].top();if(w.first0w.second1e17)puts(escaped);else puts(trapped);}}return 0;
}
