[hdu6326]Monster Hunter

考虑树是以1为中心的菊花图的情况，也即如何安排打怪兽的顺序

用二元组$(a,b)$来描述怪兽，则对于两个怪兽$(a_{1},b_{1})$和$(a_{2},b_{2})$，交换两者不会影响血量的变化量，而会改变初始血量的需求，具体即比较$\max(a_{1},a_{1}-b_{1}+a_{2})$和$\max(a_{2},a_{2}-b_{2}+a_{1})$

如果能证明传递性，那么以此进行排序即可

观察上述式子，可以得到以下信息：

1.$a\le b$的怪兽优于$a>b$的怪兽

2.对于$a\le b$的怪兽，$a$小的怪兽优于$a$大的怪兽

3.对于$a>b$的怪兽，$b$大的怪兽优于$b$小的怪兽

（代入均可证明）

进而上述信息足以比较，同时也具有传递性，即得证

回到原问题，有一个比较经典的套路：

考虑当前最优的位置，其父亲的怪兽被打死后一定会打其（注意怪兽只会被消除而不会增加），进而不妨将其与父亲合并（先打父亲再打其），合并方式参考之前

关于过程的维护，可以用一个并查集+set实现

时间复杂度为$o(n\log n)$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 100005

 4 #define ll long long

 5 struct Data{

 6     ll a,b;

 7     bool operator < (const Data &k)const{

 8         if ((a<=b)!=(k.a<=k.b))return a<=b;

 9         if (a<=b)return a<k.a;

10         return b>k.b;

11     }

12 }a[N];

13 vector<int>v[N];

14 set<pair<Data,int> >S;

15 int t,n,x,y,fa[N],f[N];

16 Data merge(Data x,Data y){

17     ll a=max(x.a,x.a-x.b+y.a);

18     return Data{a,x.b+y.b-x.a-y.a+a};

19 }

20 int find(int k){

21     if (k==f[k])return k;

22     return f[k]=find(f[k]);

23 }

24 void dfs(int k,int f){

25     fa[k]=f;

26     for(int i=0;i<v[k].size();i++)

27         if (v[k][i]!=f)dfs(v[k][i],k);

28 }

29 void merge(int x,int y){

30     x=find(x),y=find(y);

31     if (x!=1)S.erase(make_pair(a[x],x));

32     f[y]=x,a[x]=merge(a[x],a[y]);

33     if (x!=1)S.insert(make_pair(a[x],x));

34 }

35 int main(){

36     scanf("%d",&t);

37     while (t--){

38         scanf("%d",&n);

39         a[1]=Data{0,0},S.clear();

40         for(int i=1;i<=n;i++)v[i].clear();

41         for(int i=2;i<=n;i++){

42             scanf("%lld%lld",&a[i].a,&a[i].b);

43             S.insert(make_pair(a[i],i));

44         }

45         for(int i=1;i<n;i++){

46             scanf("%d%d",&x,&y);

47             v[x].push_back(y);

48             v[y].push_back(x);

49         }

50         dfs(1,0);

51         for(int i=1;i<=n;i++)f[i]=i;

52         for(int i=1;i<n;i++){

53             int x=(*S.begin()).second;

54             S.erase(S.begin());

55             merge(fa[x],x);

56         }

57         printf("%lld\n",a[1].a);

58     }

59     return 0;

60 }

巴特西

[hdu6326]Monster Hunter

最新文章

热门文章