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个询问所得到的总和最大。
思路：贪心即可，显然，对于询问越频繁的位置设的数越大越好，可以用线段树将每个位置询问的次数求出来，将原数列排序之后，找到询问数最大的位置将答案加上询问次数*当前最大数，然后将这个位置清零，继续寻找最大值即可。
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 100010using 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;}