前言
掉大坑了。
题目
链接就不给了。
题目大意
给定一棵 \(n\) 个点的树,每个点上有两个权值 \(a_i,b_i\),每次可以选择一个点,条件是它的所有祖先都已经被选择过,这样可以组成一个排列 \(p_i\),令其代价为:
\[\sum_{i=1}^n(b_{p_i}\times \sum_{j=i+1}^na_{p_j}) \]求最大代价。
\(1\le n\le 3\times 10^5;1\le a_i,b_i\le 5000;1\le f_i<i.\)
\(f_i\) 是 \(i\) 节点的父亲,似乎保证了 \(a_1=b_1=0.\)
样例
样例输入1
4
1 1 2
0 0
3 1
5 1
4 1
样例输出1
14
不会还指望我再搬几个样例吧?
讲解
首先我们不难推出优先选 \(\frac{b_i}{a_i}\) 最大的最优,这个只需要随便写个式子就好。
然后我就掉进了一个大坑,我觉得既然都有这个性质了,那么正解一定是某个妙妙贪心,说不定有反悔什么的。
然后我就无了。
如果不走偏的话其实正解也不难想,我们还是看上面那个东西,抛开祖先优先的限制不看,先选 \(\frac{b_i}{a_i}\) 最大的最优,但是如果有这个限制呢?
首先祖先一定是先选的,这毋庸置疑,然后你想选的这个最大值如果可以选了,一定会立即选它!所以我们可以考虑把最大值的那个点和它的祖先合并起来。
反复合并,直到只剩一个点,每次合并产生 \(b_{F_i}\times a_i\) 的贡献。
注意这里的 \(F_i\) 不是 \(f_i\),因为它的父亲可能已经和它的爷爷合并了,所以这个 \(F_i\) 是它的祖先中没有被合并的最近的那个点,用并查集实现。
时间复杂度 \(O(n\log_2n)\),瓶颈在堆。
代码
//12252024832524
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 300005;
int n,f[MAXN];
LL ans;
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Min(T x){return x < 0 ? -x : x;}
LL a[MAXN],b[MAXN];
struct node
{
LL a,b;int ID;
bool operator < (const node &px)const{
return b*px.a < px.b*a;
}
};
priority_queue<node> q;
int F[MAXN];
int findSet(int x){if(F[x]^x)F[x] = findSet(F[x]);return F[x];}
void unionSet(int u,int v)
{
u = findSet(u); v = findSet(v);
if(u^v) F[u] = v;
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
n = Read();
for(int i = 1;i <= n;++ i) F[i] = i;
for(int i = 2;i <= n;++ i) f[i] = Read();
for(int i = 1;i <= n;++ i) a[i] = Read(),b[i] = Read();
for(int i = 2;i <= n;++ i) q.push(node{a[i],b[i],i});
while(!q.empty())
{
node t = q.top(); q.pop();
if(t.a^a[t.ID] || t.b^b[t.ID]) continue;
int fa = findSet(f[t.ID]);
if(!fa) continue;
unionSet(t.ID,fa);
ans += b[fa] * a[t.ID];
a[fa] += a[t.ID]; b[fa] += b[t.ID];
q.push(node{a[fa],b[fa],fa});
}
Put(ans);
return 0;
}