2014
03-13

# Magic tree

Sailormoon girls have a beautiful garden, though there is only a tree in it. The tree is quite magic that it will grow different fruits to fit gilrs’ demands (xq likes bananas best, wj prefers to kiwi fruits and lff loves tomatoes).
Besides these, the tree has N forks which are connected by branches, girls mark the forks by 1 to N and the root is always marked by 1. Fruits will grow on the forks and every fork will grow several fruits. But the tree is too strange that it has many branches(even between two nodes may have more than one branch). In order to pick fruits more convenient and watch more clearly, Sailormoon girls want to cut extra branches by using minimum cost, after that, they also want to know how many fruits are there in a sub-tree. The trouble is that the tree will grow new fruits and girls will pick up some ones from the tree. Can you help them?

Input contains multiple cases. Each case contains several lines.
The first line contains two integers N, M(N<=100,000, M<=151,000), representing the number of forks and the number of branches in the tree.
The following M lines each has three integers u, v and c, which means fork u and fork v are connected by a branch, if you want to cut it, you have to cost c (arbitrary two c will be different, c<=200,000).
The next line contains an integer P, representing the operations following.
"G x y" which means the fork x will grow y more fruits ;
"C x" which means girls will pick all fruits on the fork x;
"Q x" which means girls want to know the number of fruits in the sub-tree above the fork x, including the fruits (if exists) on the fork x.
Note the tree is empty at the beginning, every number will not exceed the range of integer.

Input contains multiple cases. Each case contains several lines.
The first line contains two integers N, M(N<=100,000, M<=151,000), representing the number of forks and the number of branches in the tree.
The following M lines each has three integers u, v and c, which means fork u and fork v are connected by a branch, if you want to cut it, you have to cost c (arbitrary two c will be different, c<=200,000).
The next line contains an integer P, representing the operations following.
"G x y" which means the fork x will grow y more fruits ;
"C x" which means girls will pick all fruits on the fork x;
"Q x" which means girls want to know the number of fruits in the sub-tree above the fork x, including the fruits (if exists) on the fork x.
Note the tree is empty at the beginning, every number will not exceed the range of integer.

3 2
1 2 4
1 3 5
7
G 1 1
G 2 1
G 3 1
Q 1
C 2
Q 2
Q 3

3
0
1

View Code

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int MAXN = 100010;
int spos[MAXN],epos[MAXN],sum[MAXN],w[MAXN];
int n,f[MAXN],index;
bool vis[MAXN];
struct edge
{
int u,v,w;
edge(int a=0,int b=0,int c=0):u(a),v(b),w(c){}
bool friend operator<(const edge a,const edge b)
{
return a.w<b.w;
}
};
priority_queue<edge> Q;
vector<int> g[MAXN];
void init()
{
for(int i=0;i<=n;i++)
{
f[i]=i;
w[i]=sum[i]=0;
g[i].clear();
}
}
int find(int x)
{
if(x==f[x])
return f[x];
f[x]=find(f[x]);
return f[x];
}
void Union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b) return ;
f[a]=b;
g[x].push_back(y);//重新构建树
g[y].push_back(x);
}
void Kruskal()//将所有边压入优先队列，再取出所有边合并，求最大生成树
{
while(!Q.empty())
{
Union(Q.top().u,Q.top().v);
Q.pop();
}
}
int lowbit(int x)//这里往下三个函数就是树状数组的模板函数了，就不多说了
{
return x&(-x);
}
{
while(x<=n)
{
x+=lowbit(x);
}
}
int get_sum(int x)
{
int ret=0;
while(x!=0)
{
ret+=sum[x];
x-=lowbit(x);
}
return ret;
}
void dfs(int u)
{
spos[u]=index;//记录子树的起始位置
vis[u]=true;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!vis[v])
{
index++;
dfs(v);
}
}
epos[u]=index;//记录子树的终点位置
}
int main()
{
int m,k,a,b,c;
char str[5];
while(scanf("%d %d",&n,&m)==2)
{
init();
while(m--)
{
scanf("%d %d %d",&a,&b,&c);
Q.push(edge(a,b,c));
}
Kruskal();
index=1;
memset(vis,false,sizeof(vis));
dfs(1);
scanf("%d",&m);
while(m--)
{
scanf("%s",str);
if(str[0]=='G')
{
scanf("%d %d",&a,&c);
modify(spos[a],c);
w[a]+=c;
}
else if(str[0]=='C')
{
scanf("%d",&a);
modify(spos[a],-w[a]);
w[a]=0;
}
else {
scanf("%d",&a);
int ans=get_sum(epos[a])-get_sum(spos[a]-1);
printf("%d\n",ans);
}
}
}
return 0;
}

1. #include <stdio.h>
int main()
{
int n,p,t[100]={1};
for(int i=1;i<100;i++)
t =i;
while(scanf("%d",&n)&&n!=0){
if(n==1)
printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
else {
if(n%4) p=n/4+1;
else p=n/4;
int q=4*p;
printf("Printing order for %d pages:n",n);
for(int i=0;i<p;i++){
printf("Sheet %d, front: ",i+1);
if(q>n) {printf("Blank, %dn",t[2*i+1]);}
else {printf("%d, %dn",q,t[2*i+1]);}
q–;//打印表前
printf("Sheet %d, back : ",i+1);
if(q>n) {printf("%d, Blankn",t[2*i+2]);}
else {printf("%d, %dn",t[2*i+2],q);}
q–;//打印表后
}
}
}
return 0;
}