2016-2017 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2016) F dfs序+树状数组

Performance Review
Employee performance reviews are a necessary evil in any company. In a performance review, employees give written feedback about each other on the work done recently. This feedback is passed up to their managers which then decide promotions based on the feedback received. Maria is in charge of the performance review system in the engineering division of a famous company. The division follows a typical structure. Each employee (except the engineering director) reports to one manager and every employee reports directly or indirectly to the director. Having the managers assessing the performance of their direct reports has not worked very well. After thorough research, Maria came up with a new performance review system. The main idea is to complement the existing corporate structure with a technical rank for each employee. An employee should give feedback only about subordinates with lower technical level. Hence, the performance review will work as follows. Employees prepare a summary of their work, estimate how much time it takes to review it, and then request their superiors with higher technical rank to review their work. Maria is very proud of this new system, but she is unsure if it will be feasible in practice. She wonders how much time each employee will waste writing reviews. Can you help her out?
Task
Given the corporate structure of the engineering division, determine how much time each employee will spend writing performance reviews.
Input
The rst line of input has one integer E, the number of employees, who are conveniently numbered between 1 and E. The next E lines describe all the employees, starting at employee 1 until employee E. Each line contains three space-separated integers mi ri ti, the manager, the technical rank and the expected time to perform the review of employee i. The engineering director has no manager, represented with mi = −1. The other employees have mi between 1 and E.
SWERC'2016 Universidade do Porto 13
Problem F Problem F
Constraints 1 ≤ E ≤ 100000 Number of employees 1 ≤ ri ≤ 100000 Technical rank of each employee 1 ≤ ti ≤ 100000 Expected time to perform each review
Output
The output contains E lines. Line i has the time employee i will spend writing reviews.
Sample Input
5

4 4 80

1 1 40

-1 10 60

3 5 50

4 8 70
Sample Output

240

120

题意：给你一棵树每个结点有r，t值现在求所有结点i的子树中的r值小于i点的r值的所有结点的t值之和

题解：dfs序列+树状数组结点按照r值排序 r值相同的深度小的排前面。依次处理结点，将子树的操作转换到区间上。树状数组中存的是结点序号（dfs遍历序号in[root]）

 #include<bits/stdc++.h>

 using namespace std;

 #define ll __int64

 #pragma comment(linker, "/STACK:102400000,102400000")

 ll n;

 ll a,b,c;

 ll pre[];

 ll in[];

 ll out[];

 ll nedge=;

 ll dfn=;

 ll dep[];

 map<ll,ll>mp;

 struct node

 {

     ll pre;

     ll to;

 }N[*];

 struct dian

 {

    ll w;

    ll you;

    ll id;

 }M[],MM[];

 ll tree[];

 bool cmp(struct dian aaa,struct dian bbb)

 {

     if(aaa.you<bbb.you)

         return true;

     else

     {

         if(aaa.you==bbb.you)

             return dep[in[aaa.id]]<dep[in[bbb.id]];

     }

     return false;

 }

 void add(ll from,ll to)

 {

     nedge++;

     N[nedge].to=to;

     N[nedge].pre=pre[from];

     pre[from]=nedge;

 }

 void getdfs(ll root,int de)

 {

     in[root]=++dfn;

     MM[dfn]=M[root];

     dep[dfn]=de;

     mp[root]=;

     for(ll i=pre[root];i;i=N[i].pre){

         if(mp[N[i].to])

             continue;

         getdfs(N[i].to,de+);

     }

     out[root]=dfn;

 }

 ll lowbit(ll xx)

 {

     return xx&(-xx);

 }

 void add2 (ll x,ll y)

 {

     for(ll i=x;i<=n;i+=lowbit(i))

         tree[i]+=y;

 }

 ll getsum (ll x)

 {

     ll ans=;

     for(ll i=x;i>=;i-=lowbit(i))

         ans+=tree[i];

     return ans;

 }

 int main()

 {

     scanf("%I64d",&n);

     memset(tree,,sizeof(tree));

     memset(pre,,sizeof(pre));

     nedge=;

     ll ro=;

     for(ll i=;i<=n;i++)

     {

         scanf("%I64d %I64d %I64d",&a,&b,&c);

         M[i].w=c;

         M[i].you=b;

         M[i].id=i;

         if(a==-){

             ro=i;

             continue;

             }

         add(a,i);

         add(i,a);

     }

     getdfs(ro,);

     ll ans[];

     sort(MM+,MM++n,cmp);

     for(ll i=;i<=n;i++)

     {

         ll l,r;

         l=in[MM[i].id];

         r=out[MM[i].id];

         ans[MM[i].id]=getsum(r)-getsum(l);

         add2(l,MM[i].w);

     }

     for(ll i=;i<=n;i++)

         printf("%I64d\n",ans[i]);

     return ;

 }

巴特西

2016-2017 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2016) F dfs序+树状数组

最新文章

热门文章