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;
}