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);
}
void modify(int x,int add)
{
while(x<=n)
{
sum[x]+=add;
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. 我这个是说的101,不是说你，只是回复的时候少打了个它。好吧，我来解释下事情的前因后果。忘记在哪个帖子了，他贴了那一大堆的各种对国家、ZF不满的话题回复我，然后把，我就回复了“呵呵，你这个我在其他论坛也看到了，就不要再贴到这里了。”然后，他就说我是五毛啊

2. 我这个是说的101,不是说你，只是回复的时候少打了个它。好吧，我来解释下事情的前因后果。忘记在哪个帖子了，他贴了那一大堆的各种对国家、ZF不满的话题回复我，然后把，我就回复了“呵呵，你这个我在其他论坛也看到了，就不要再贴到这里了。”然后，他就说我是五毛啊

3. 我这个是说的101,不是说你，只是回复的时候少打了个它。好吧，我来解释下事情的前因后果。忘记在哪个帖子了，他贴了那一大堆的各种对国家、ZF不满的话题回复我，然后把，我就回复了“呵呵，你这个我在其他论坛也看到了，就不要再贴到这里了。”然后，他就说我是五毛啊

4. 我这个是说的101,不是说你，只是回复的时候少打了个它。好吧，我来解释下事情的前因后果。忘记在哪个帖子了，他贴了那一大堆的各种对国家、ZF不满的话题回复我，然后把，我就回复了“呵呵，你这个我在其他论坛也看到了，就不要再贴到这里了。”然后，他就说我是五毛啊

5. 我这个是说的101,不是说你，只是回复的时候少打了个它。好吧，我来解释下事情的前因后果。忘记在哪个帖子了，他贴了那一大堆的各种对国家、ZF不满的话题回复我，然后把，我就回复了“呵呵，你这个我在其他论坛也看到了，就不要再贴到这里了。”然后，他就说我是五毛啊

6. 我这个是说的101,不是说你，只是回复的时候少打了个它。好吧，我来解释下事情的前因后果。忘记在哪个帖子了，他贴了那一大堆的各种对国家、ZF不满的话题回复我，然后把，我就回复了“呵呵，你这个我在其他论坛也看到了，就不要再贴到这里了。”然后，他就说我是五毛啊

7. 我这个是说的101,不是说你，只是回复的时候少打了个它。好吧，我来解释下事情的前因后果。忘记在哪个帖子了，他贴了那一大堆的各种对国家、ZF不满的话题回复我，然后把，我就回复了“呵呵，你这个我在其他论坛也看到了，就不要再贴到这里了。”然后，他就说我是五毛啊

8. 我这个是说的101,不是说你，只是回复的时候少打了个它。好吧，我来解释下事情的前因后果。忘记在哪个帖子了，他贴了那一大堆的各种对国家、ZF不满的话题回复我，然后把，我就回复了“呵呵，你这个我在其他论坛也看到了，就不要再贴到这里了。”然后，他就说我是五毛啊

9. 我这个是说的101,不是说你，只是回复的时候少打了个它。好吧，我来解释下事情的前因后果。忘记在哪个帖子了，他贴了那一大堆的各种对国家、ZF不满的话题回复我，然后把，我就回复了“呵呵，你这个我在其他论坛也看到了，就不要再贴到这里了。”然后，他就说我是五毛啊

10. 我这个是说的101,不是说你，只是回复的时候少打了个它。好吧，我来解释下事情的前因后果。忘记在哪个帖子了，他贴了那一大堆的各种对国家、ZF不满的话题回复我，然后把，我就回复了“呵呵，你这个我在其他论坛也看到了，就不要再贴到这里了。”然后，他就说我是五毛啊

11. 我这个是说的101,不是说你，只是回复的时候少打了个它。好吧，我来解释下事情的前因后果。忘记在哪个帖子了，他贴了那一大堆的各种对国家、ZF不满的话题回复我，然后把，我就回复了“呵呵，你这个我在其他论坛也看到了，就不要再贴到这里了。”然后，他就说我是五毛啊

12. #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;
}

13. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.

14. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

15. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。