codeforces round 169 div2 题解

http://codeforces.com/problemset/problem/276/A

A：题意：有n家餐馆，a[1]~a[n],在每家餐馆有一个欢乐度fi和时间ti，给你一个常数k，对于每家餐馆若ti>k,则获得fi-（ti-k）点欢乐度，否则增加fi点欢乐度，问在哪家餐馆吃饭获得的欢乐度最大。。。。

思路：SB题，直接枚举不解释。。。

http://codeforces.com/contest/276/problem/B

B:题意：首先给一个字符串，博弈，两个人轮流从字符串中随意删除一个元素，当一个人取之前，当前字符串是一个回文串时，这个人取得胜利，问对于给定的字符串，事先取的人必胜还是后取的人必胜。

思路：首先，要搞明白什么样的字符串是回文串，设字符串的长度为len，因为回文串是左右对称的，则若len为偶数，则字符串的每个字符个数均为偶数，若len为奇数，则除了中间的那个字符的总个数为奇数外，其他也均为偶数，所以游戏就是要避免达到总个数为奇数的字符的个数为0或1（。。。有点拗口哈。。。），我们一开始把所有字符的个数求出来，找出其个数为奇数的字符的个数，设为num,若num为0或1，则显然先手必胜，否则，我们先考虑num=2，这时先手若取走一个字符使num-1，则这时后手就胜利了，所以先手不能使num-1，只能去一个字符使num+1，这时后手就可以去一个字符将num-1，这时又回到了开始的状态，我们一直这样取下去，因为字符越来越少，最后会变成只剩下2个字符个数为奇数，其他都为0，这时先手不得不去掉一个字符使num=1，这时还是后手胜利，所以对于num=2时是后手必胜，我们可以一直按这个策略，则对于num>=2，num为偶数时，后手必胜，否则先手必胜。

http://codeforces.com/contest/276/problem/C

C:题意：给你n个数，q个询问，询问在[l,r]区间数的总和，要求重新排列这n个数，使得这q个询问所得到的总和最大。

思路：贪心即可，显然，对于询问越频繁的位置设的数越大越好，可以用线段树将每个位置询问的次数求出来，将原数列排序之后，找到询问数最大的位置将答案加上询问次数*当前最大数，然后将这个位置清零，继续寻找最大值即可。

http://codeforces.com/contest/276/problem/D

D:题意：给你两个数L和R，（L<=R），问在L与R之间找两个数x和y使得x^y最大。

思路：我们将L和R用二进制表示出来，从最高位开始，依次遍历，直到找到第一处不相等的位置，设为第po位，对于比po更高的位，因为我们必须使得x,y在L与R之间，所以异或只能为0（因为po是从高到低第一位满足L[po]!=R[po]的位）。对于第po位，我们不妨设x[po]=1,y[po]=0，这样一来，不管以后怎么设置，x不会小于L，且y不会大于R,则对于以后的每一位，我们设x为0,y为1，则可以保证满足x,y在L,R之间，且这时候显然x^y最大,答案为(1<<(po+1)-1)。

http://codeforces.com/contest/276/problem/E

E：题意：给你一棵树，这棵树除了根节点外，其他的节点的度数不会超过2，每个节点上有一个数，初始时为0，现有两种操作：

1：0 v x d ,表示将距离V节点长度不超过d的所有节点上的数加上x。

2 :  1 v ， 表示询问v节点上的数为多少。

思路：仔细分析题目条件可看看出，将根节点去掉之后，整棵树就变成了一条条的链，于是我们可以把所有的链放进线段树中维护，根节点另外讨论，我们可按dfs序列将除根节点外的所有点放进线段树中，当我们更新一个节点时，我们找到对应的链在线段树中的位置，更新该节点以上以下d距离的节点，这时有可能会更新到根节点上，甚至跳过根节点更新到其他链中去，所以我们还要在维护一个数据结构，保存距离根节点deep距离的点（也就是深度）增加的值为多少（我用的树状数组），于是我们更新一个点分成了两个步骤，首先在当前脸上更新，若需要更新到根节点或其他链，我们更新树状数组，并且还要讲当前链中多加的值减回来，这个应该很好理解吧，算一下就出来了。对于询问我们也分为两部分，该点所在链中对应的值加上树状数组中保存的增量，注意对于根节点要另外讨论。代码如下所示。（写的屎长，其实可以就用两个树状数组的，当时傻逼了。。凑合看吧。。。）

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#define maxn 100010
using namespace std;
#define mid ((t[p].l+t[p].r)>>1)
#define ls (p<<1)
#define rs (ls|1)
//以下为树状数组
int c[maxn];
int lowbit(int x)
{
    return x&(-x);
}
void addval(int x,int val,int n)
{
    while(x<=n)
    {
        c[x]+=val;
        x+=lowbit(x);
    }
}
int getsum(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
 //以下为线段树
struct node
{
    int l,r;
    int val;
}t[maxn<<2];
void pushdown(int p)
{
    if(t[p].val)
    {
        t[ls].val+=t[p].val;
        t[rs].val+=t[p].val;
        t[p].val=0;
    }
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    t[p].val=0;
    if(l==r)
    {
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void add(int p,int l,int r,int val)
{
    if(t[p].l==l&&t[p].r==r)
    {
        t[p].val+=val;
        return;
    }
    pushdown(p);
    if(r<=mid)
    add(ls,l,r,val);
    else if(l>mid)
    add(rs,l,r,val);
    else
    {
        add(ls,l,mid,val);
        add(rs,mid+1,r,val);
    }
}
int getval(int p,int x)
{
    if(t[p].l==t[p].r)
    return t[p].val;
    pushdown(p);
    if(x>mid)
    return getval(rs,x);
    else
    return getval(ls,x);
}
//以下是建树
struct edge
{
    int to;
    int next;
}e[maxn<<1];
int box[maxn],cnt;
void init()
{
    memset(box,-1,sizeof(box));
    cnt=0;
}
void add(int from,int to)
{
    e[cnt].to=to;
    e[cnt].next=box[from];
    box[from]=cnt++;
}
int dep[maxn],pre[maxn],child[maxn],scc=0;
int max(int a,int b)
{
    return a>b?a:b;
}
void dfs(int now,int deep)
{
    dep[now]=deep;
    pre[now]=++scc;
    child[now]=scc;
    int tt,w;
    for(tt=box[now];tt+1;tt=e[tt].next)
    {
        w=e[tt].to;
        if(!pre[w])
        {
            dfs(w,deep+1);
            child[now]=max(child[now],child[w]);
        }
    }
}
int inout[maxn];
int min(int a,int b)
{
    return a<b?a:b;
}
int main()
{
    freopen("dd.txt","r",stdin);
    int n,q,i,a,b,root,tmp=0;
    memset(c,0,sizeof(c));
    memset(inout,0,sizeof(inout));
    scanf("%d%d",&n,&q);
    init();
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
        inout[a]++;
        inout[b]++;
    }
    for(i=1;i<=n;i++)
    {
        if(inout[i]>tmp)
        {
            tmp=inout[i];
            root=i;
        }
    }
   dfs(root,0);
   build(1,1,n);
   while(q--)
   {
       int t,v,x,d;
       scanf("%d",&t);
       if(t)
       {
           scanf("%d",&v);
           int ans=getval(1,pre[v])+getsum(n+1-dep[v]);
           printf("%d\n",ans);
       }
       else
       {
           scanf("%d%d%d",&v,&x,&d);
           if(v!=root)
           add(1,pre[v],min(child[v],pre[v]+d),x);
           if(dep[v]>d)
           {
               add(1,pre[v]-d,pre[v]-1,x);
           }
           else
           {
               if(pre[v]-dep[v]+1<=pre[v]-1)
               add(1,pre[v]-dep[v]+1,pre[v]-1,x);
               addval(n+1-d+dep[v],x,n+1);
               if(v!=root&&pre[v]-dep[v]+1<=min(child[v],pre[v]-2*dep[v]+d))
               add(1,pre[v]-dep[v]+1,min(child[v],pre[v]-2*dep[v]+d),-x);
           }
       }
   }
    return 0;
}