A：枚舉 B：博弈，當時有點蒙的感覺。 首先統計每個字母的個數，如果奇數個的有x個，當x<=1時，顯然先手已勝。 否則當x為奇數時，先手只要先拿走一個個數奇數的字母，那麼後手不管取什麼，個數為奇數的都要變化1。所以總是在後手處理之後，奇數個數為1，先手勝。 同理x為偶數的時候，先手不管怎麼取，奇數個數都為奇數，同上，後手勝。 C：區間更新，用線段樹也行，victoria曾經給OI上課時說到一種標記法，還好當時旁聽了 D：一直WA，卡了很久。從高位往低位分析，找到第一位L,R不同的位，必然是R為1，L為0。那麼之前的所有高位不管怎麼取，異或之後都為0。對於當前位，當然是a取1，b取0 (a>=b)，之後對於 b全部取1，a全部取0即可。 E：有個神奇的條件，除了1號節點，其它節點的度<=2，也就是好多 鏈，這樣就可以維護一個區間和。 當然也可能是對於1號節點以外，所有節點的度都為1，所有的鏈長度為1，這樣就很DT了。 那我們就要分為兩種情況。 對於1號節點，與1號節點相同距離的維護一個區間和。 對於每條鏈，維護一個區間和。 [cpp] #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<set> #include<stack> #include<string> #include<ctime> #include<queue> #include<cassert> #define inf 1000000005 #define M 10000005 #define N 100005 #define maxn 210005 #define eps 1e-8 #define zero(a) fabs(a)<eps #define Min(a,b) ((a)<(b)?(a):(b)) #define Max(a,b) ((a)>(b)?(a):(b)) #define pb(a) push_back(a) #define mp(a,b) make_pair(a,b) #define mem(a,b) memset(a,b,sizeof(a)) #define LL long long #define MOD 1000000007 #define sqr(a) ((a)*(a)) #define Key_value ch[ch[root][1]][0] #define test puts("OK"); #define pi acos(-1.0) #define lowbit(x) ((-(x))&(x)) #define HASH1 1331 #define HASH2 10001 #define lson step<<1 #define rson step<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; int n,q; int tot=0; int dep[N]; int col[N],row[N]; vector<int>edge[N]; vector<LL > sum; vector<vector<LL> >s; LL root=0; int max_dep=1; void init(int u,int pre){ for(int i=0;i<edge[u].size();i++){ int v=edge[u][i]; if(v==pre) continue; if(u==1){ tot++; row[v]=1; col[v]=tot; dep[tot]=1; } else{ row[v]=row[u]+1; col[v]=col[u]; dep[col[v]]++; max_dep=max(max_dep,dep[col[v]]); } init(v,u); } } void update(vector<LL>&a,int x,int val){ for(int i=x;i>0;i-=lowbit(i)) a[i]+=val; } LL get(vector<LL>&a,int x){ LL ret=0; for(int i=x;i<a.size();i+=lowbit(i)) ret+=a[i]; return ret; } LL query(int v){ if(v==1) return root; else return get(s[col[v]],row[v])+get(sum,row[v]); } int main(){ scanf("%d%d",&n,&q); for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); edge[u].pb(v); edge[v].pb(u); } init(1,0); s.resize(tot+10); sum.resize(max_dep+10); for(int i=1;i<=tot;i++) s[i].resize(dep[i]+10); while(q--){ int k,v,x,d; scanf("%d",&k); if(!k){ scanf("%d%d%d",&v,&x,&d); int c=col[v],r=row[v]; if(v==1){ update(sum,min(max_dep,d),x); root+=x; } else{ int t=r-d; if(t>0){ update(s[c],t-1,-x); update(s[c],min(dep[c],r+d),x); } else if(t==0){ update(s[c],min(dep[c],r+d),x); root+=x; } else{ t=-t; root+=x; update(sum,min(max_dep,t),x); int L=t+1,R=min(dep[c],r+d); if(L<=R){ update(s[c],L-1,-x); update(s[c],R,x); } } } //cout<<query(1)<<" "<<query(2)<<" "<<query(3)<<endl; } else{ scanf("%d",&v); printf("%I64d\n",query(v)); } } return 0; } #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<set> #include<stack> #include<string> #include<ctime> #include<queue> #include<cassert> #define inf 1000000005 #define M 10000005 #define N 100005 #define maxn 210005 #define eps 1e-8 #define zero(a) fabs(a)<eps #define Min(a,b) ((a)<(b)?(a):(b)) #define Max(a,b) ((a)>(b)?(a):(b)) #define pb(a) push_back(a) #define mp(a,b) make_pair(a,b) #define mem(a,b) memset(a,b,sizeof(a)) #define LL long long #define MOD 1000000007 #define sqr(a) ((a)*(a)) #define Key_value ch[ch[root][1]][0] #define test puts("OK"); #define pi acos(-1.0) #define lowbit(x) ((-(x))&(x)) #define HASH1 1331 #define HASH2 10001 #define lson step<<1 #define rson step<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; int n,q; int tot=0; int dep[N]; int col[N],row[N]; vector<int>edge[N]; vector<LL > sum; vector<vector<LL> >s; LL root=0; int max_dep=1; void init(int u,int pre){ for(int i=0;i<edge[u].size();i++){ int v=edge[u][i]; if(v==pre) continue; if(u==1){ tot++; row[v]=1; col[v]=tot; dep[tot]=1; } else{ row[v]=row[u]+1; col[v]=col[u]; dep[col[v]]++; max_dep=max(max_dep,dep[col[v]]); } init(v,u); } } void update(vector<LL>&a,int x,int val){ for(int i=x;i>0;i-=lowbit(i)) a[i]+=val; } LL get(vector<LL>&a,int x){ LL ret=0; for(int i=x;i<a.size();i+=lowbit(i)) ret+=a[i]; return ret; } LL query(int v){ if(v==1) return root; else return get(s[col[v]],row[v])+get(sum,row[v]); } int main(){ scanf("%d%d",&n,&q); for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); edge[u].pb(v); edge[v].pb(u); } init(1,0); s.resize(tot+10); sum.resize(max_dep+10); for(int i=1;i<=tot;i++) s[i].resize(dep[i]+10); while(q--){ int k,v,x,d; scanf("%d",&k); if(!k){ scanf("%d%d%d",&v,&x,&d); int c=col[v],r=row[v]; if(v==1){ update(sum,min(max_dep,d),x); root+=x; } else{ int t=r-d; if(t>0){ update(s[c],t-1,-x); update(s[c],min(dep[c],r+d),x); } else if(t==0){ update(s[c],min(dep[c],r+d),x); root+=x; } else{ t=-t; root+=x; update(sum,min(max_dep,t),x); int L=t+1,R=min(dep[c],r+d); if(L<=R){ update(s[c],L-1,-x); update(s[c],R,x); } } } //cout<<query(1)<<" "<<query(2)<<" "<<query(3)<<endl; } else{ scanf("%d",&v); printf("%I64d\n",query(v)); } } return 0; }
