icontofig | 发布于 2017-02-18 21:49:25 | 阅读量 207 | 树上前缀和
发布于 2017-02-18 21:49:25 | 树上前缀和
C. Garland
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Once at New Year Dima had a dream in which he was presented a fairy garland. A garland is a set of lamps, some pairs of which are connected by wires. Dima remembered that each two lamps in the garland were connected directly or indirectly via some wires. Furthermore, the number of wires was exactly one less than the number of lamps.

There was something unusual about the garland. Each lamp had its own brightness which depended on the temperature of the lamp. Temperatures could be positive, negative or zero. Dima has two friends, so he decided to share the garland with them. He wants to cut two different wires so that the garland breaks up into three parts. Each part of the garland should shine equally, i. e. the sums of lamps' temperatures should be equal in each of the parts. Of course, each of the parts should be non-empty, i. e. each part should contain at least one lamp.

Help Dima to find a suitable way to cut the garland, or determine that this is impossible.

While examining the garland, Dima lifted it up holding by one of the lamps. Thus, each of the lamps, except the one he is holding by, is now hanging on some wire. So, you should print two lamp ids as the answer which denote that Dima should cut the wires these lamps are hanging on. Of course, the lamp Dima is holding the garland by can't be included in the answer.

Input

The first line contains single integer n (3 ≤ n ≤ 106) — the number of lamps in the garland.

Then n lines follow. The i-th of them contain the information about the i-th lamp: the number lamp ai, it is hanging on (and 0, if is there is no such lamp), and its temperature ti ( - 100 ≤ ti ≤ 100). The lamps are numbered from 1 to n.

Output

If there is no solution, print -1.

Otherwise print two integers — the indexes of the lamps which mean Dima should cut the wires they are hanging on. If there are multiple answers, print any of them.

Examples
input
62 40 54 22 11 14 2
output
1 4
input
62 40 64 22 11 14 2
output
-1
Note

The garland and cuts scheme for the first example:

 传送门:http://codeforces.com/problemset/problem/767/C

后悔卡在B题上没做这个SB题了……我的rating掉的真的惨啊。

题目大意

给一个树,树上每个节点有权值,让你把这棵树分成3个新的树,使得他们的节点权值和相等,求分割点(SPJ),如果没有方案输出-1(分割点不能是根)(至于输入格式读读英语吧,还是有好处的……)

题解

这题很简单……
按照题目要求,建出树(注意根节点的父亲是0),统计树上前缀和(别告诉我不会前缀和,序列上的前缀和搞到树上就是树上前缀和,别想多了什么树链剖分,就是把子节点权值加到父节点上然后不断上传)。
统计所有节点权值和,如果不能被3整除,直接输出-1。
首先找ans1,我们尽量往树的深处找,不然下次dfs的话就可能忽略这个子树里面的东西了。如果ans1是0或者根的话,那就直接输出-1;否则标记ans1被分割。
这时候被标记的点以下的子树我们就可以忽略了。然后重新dfs求树上前缀和,去找ans2,一旦找到一个不是0或者根的节点上标记的前缀和为我们需要的,就直接ans2就是这个节点了,直接走。如果找不到的话就输出-1。
此题有SPJ,所以输出顺序并没有什么太大关系。

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e6+5;
int n,t[maxn],sum[maxn];
struct edge{
    int to,next;
}e[maxn<<2];
int h[maxn],fa[maxn],dep[maxn],cnt = 0;
void add(int u,int v){
    e[cnt].to = v;
    e[cnt].next = h[u];
    h[u] = cnt++;
}
int b,root;bool vis[maxn];
void dfs(int now,int father,int depth){
    sum[now] = t[now];
    fa[now] = father;
    dep[now] = depth;
    for(int i = h[now];i != -1;i = e[i].next){
        if(e[i].to == father || vis[e[i].to])continue;
        dfs(e[i].to,now,depth+1);
        sum[now] += sum[e[i].to];
    }
    return;
}
int main(){
    memset(h,-1,sizeof(h));
    memset(vis,0,sizeof(vis));
    n = get_num();
    int p = 0;
    for(int i = 1;i <= n;++i){
        fa[i] = get_num();
        if(!fa[i])root = i;
        t[i] = get_num();
        p += t[i];
        add(i,fa[i]);
        add(fa[i],i);
    }
    dfs(root,root,0);
    if(p % 3){
        printf("-1\n");
        return 0;
    }
    p /= 3;
    int ans1 = 0;
    for(int i = 1;i <= n;++i){
        if(sum[i] == p){
            if(!ans1)ans1 = i;
            else if(dep[ans1] < dep[i])ans1 = i;
        }
    }
    if(ans1 == 0 || ans1 == root){
        printf("-1\n");
        return 0;
    }
    vis[ans1] = 1;
    int ans2 = 0;
    dfs(root,root,0);
    for(int i = 1;i <= n;++i)
        if(sum[i] == p && !vis[i]){
            ans2 = i;
            break;
        }
    if(ans2 == 0 || ans2 == root){
        printf("-1\n");
        return 0;
    }
    printf("%d %d\n",min(ans1,ans2),max(ans1,ans2));
    return 0;
}
​

内容更新于: 2017-02-18 21:49:25
链接地址: http://blog.leanote.com/post/icontofig/7388a915ed16

上一篇: NOI2005 维修数列

下一篇: SDOI2013费用流

207 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航